[491][中等][DFS] 递增子序列

题目描述

491. 递增子序列

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

示例:

输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

说明:

• 给定数组的长度不会超过15。

• 数组中的整数范围是 [-100,100]。

• 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。

解题思路

DFS

对于一个已有的递增序列, 判断当前值能否加入到这个递增序列当中, 只需与最后一个值比较. 如果不大于, 则pass, 继续向下搜索. 但如果大于, 可以有两个选择:

• 将这个值加入到递增序列当中, 继续向下搜索

• 无视这个值, 跳过, 然后向下搜索

按照这个思路构建DFS函数, 停止条件为搜索的索引越界. 使用LRU缓存中间结果, 避免重复搜索. 为了使用LRU, 将递增序列使用字符串表示, 使用特殊符号(下面的程序中使用的是;字符)分隔数字.

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = set()

        @lru_cache(None)
        def dfs(temp, i):
            if i >= n:
                return
            last = int(temp.split(';')[-1])
            if nums[i] >= last:
                new_temp = temp + ";{}".format(str(nums[i]))
                res.add(new_temp)
                dfs(new_temp, i + 1)
                dfs(temp, i + 1)
            else:
                dfs(temp, i + 1)

        for j in range(n):
            dfs(str(nums[j]), j + 1)

        return [[int(t) for t in single.split(';')]for single in res]