491. Non-decreasing Subsequences.md

491. Non-decreasing Subsequences

https://leetcode.com/problems/non-decreasing-subsequences/

solution

• 注意：本题dfs里不能有return，要取树上的所有节点。如果return遇到一层符合的就返回了
• 原去重思路：排序+判断相等无法使用，因为无法排序。另一种去重思路：保存后保存

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        path = []
        res = []
        self.dfs(nums, path, res, start=0)
        return res

    def dfs(self, nums, path, res, start):
        if len(path) > 1:
            res.append(path[:])

        used = set()  # 记录本层元素是否重复使用，新一层used都会被清空。因此进来之后才刚刚定义，所以不需要最后回溯时处理
        for i in range(start, len(nums)):
            if nums[i] in used:
                continue
            if path and nums[i] < path[-1]:
                continue

            used.add(nums[i])
            path.append(nums[i])
            self.dfs(nums, path, res, i+1)
            path.pop()

时间复杂度：O(n⋅2^n)
空间复杂度：O(2^n)