递增子序列-回溯491-python

没看答案。

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

        def backtrack(start):
            nonlocal track
            valid = [] # 记录以某个数字开头的选择在之前有没有被做过了

            if len(track) > 1:
                res.append(track[:])
            
            for cho in range(start, n):
                # 记录以nums[cho]开头的选择在之前有没有被选择过了，以避免重复
                if cho > start and nums[cho] in valid:
                    continue
                valid.append(nums[cho])
                
                if not track or nums[cho] >= track[-1]:
                    track.append(nums[cho])
                    backtrack(cho+1)
                    track.pop()
        
        backtrack(0)
        return res