leetcode491 递增子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例 2：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]

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

    def dfs(self, nums, result, path, index):
        n = len(nums)
        # 满足把path添加到结果的条件的时候，不能return，因为path后还可以继续添加
        if len(path) >= 2:
            result.append(path.copy())
        if index >= n:
            return

        used_set = set()
        for i in range(index, n):
            # 一般的含有重复元素的时候，只需要nums[i]!=nums[i-1]来去重
            # 这个方法的前提是数组实现已经排序过了，
            # 因此只要数组里面重复的东西都会挨在一起。
            # 但是这里是子序列问题，不允许重新排序，元素之间可以有任意多跳，因此只要以前使用过都不行
            if nums[i] in used_set:
                continue
            if (len(path) == 0) or (nums[i] >= path[-1]):
                used_set.add(nums[i])
                path.append(nums[i])
                self.dfs(nums, result, path, i + 1)
                path.pop()