代码随想录算法训练营-回溯算法|491.递增子序列

491. 递增子序列

 不对原数组进行排序，利用set对同层的子集进行去重。

 1 class Solution:
 2     def findSubsequences(self, nums):
 3         result = []
 4         path = []
 5         self.backtracking(nums, 0, path, result)
 6         return result
 7     
 8     def backtracking(self, nums, startIndex, path, result):
 9         if len(path) > 1:
10             result.append(path[:])  # 注意要使用切片将当前路径的副本加入结果集
11             # 注意这里不要加return，要取树上的节点
12         
13         uset = set()  # 使用集合对本层元素进行去重
14         for i in range(startIndex, len(nums)):
15             if (path and nums[i] < path[-1]) or nums[i] in uset:
16                 continue
17             
18             uset.add(nums[i])  # 记录这个元素在本层用过了，本层后面不能再用了
19             path.append(nums[i])
20             self.backtracking(nums, i + 1, path, result)
21             path.pop()