491. 递增子序列
给你一个整数数组
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]]
提示：
1 <= nums.length <= 15
100 <= nums[i] <= 100
法1 回溯
思路
同子集类似，只不过本题目需要找到的子集为递增子集，所以对于重复的元素不能排序，而是采用一个used数组记录同一层的相同的元素是否被第二次使用。
题解
class Solution: def findSubsequences(self, nums: List[int]) -> List[List[int]]: self.res = [] self.backtrack(path=[], nums=nums, start=0) return self.res def backtrack(self, path, nums, start): if len(path) >= 2: self.res.append(path[:]) used = [] for i in range(start, len(nums)): # （当前path为空 or 当前path最后一个元素小于nums[i]） 且 当前nums[i] 没有在同层使用过 if len(path) == 0 or (len(path)>0 and path[-1]<=nums[i]): if nums[i] not in used: used.append(nums[i]) path.append(nums[i]) self.backtrack(path, nums, i+1) path.pop()