文章目录
- 题目描述
- 思路分析
- 完整代码
题目描述
给你一个整数数组 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.确定函数参数：
这个题的参数没什么变化，就还是那个startindex，前面说过无数遍了，就不说了。
2.确定终止条件：
这是这道题比较有意思的地方，终止条件可以理解为，收集结果的地方，实际上对于包括之前的子集问题，是没有终止条件的，就是任何子节点的结果都需要，而这道题唯一需要注意的两个地方就是，当前记录的答案里面是不是的元素是不是大于1个，而且是不是递增的。
是否递增可以去for循环里控制，这里只需要判断记录的答案里是不是元素是不是有2个及以上就行了。
if len(path) >=2:
res.append(path[:]) #注意这里不要加return，要取树上的节点
3.确定循环体：
因为这道题需要去重，而又不能用之前组合总和2里的那个去重思路，因为这是找子序列，不能排序，排序之后顺序就乱了。
两个去重思路，一个是收集答案的时候，看看答案里有没有重复的，没有的话再收集。这个思路比较简单。
另一个思路就是，建立一个数组repeat，记录本层树层使用过的元素，如果使用过就直接continue。
细节;
这里有一个需要注意的地方，就是去重数组repeat在哪里定义的问题，看下面的代码可以看到，我的答案集合res,和记录路径元素集合path都是在外面函数定义的，而reapeat是在回溯函数里定义的。
要知道repeat去重的是树层，也就是本层里重复的元素，纵向的重复是不记录的，关于这点，在之前的组合里有说过，这就不细说了，总之就是一个答案内的元素可以重复，多个答案之间不能相同。
而每一次向下一层走的时候都是一次递归，向下走一次(纵向）就是一个新的一层(横向)，所以repeat = [] 定义在回溯，递归的函数里，每次向下走 就让他清空一次，记录新一层重复的值。
完整代码
思路1：
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def backtrack(startindex):
# 确定终止条件
if len(path) >=2:
if path[-1]>=path[-2] :
temp = path[:]
if temp not in res:
res.append(temp)
else:
return
for i in range(startindex,len(nums)):
path.append(nums[i])
backtrack(i+1)
path.pop()
backtrack(0)
return res
思路2：
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def backtrack(startindex):
# 确定终止条件
repeat = []
if len(path) >=2:
res.append(path[:])
for i in range(startindex,len(nums)):
if nums[i] in repeat:
continue
if len(path) >=1 and path[-1] > nums[i]:
continue
repeat.append(nums[i])
path.append(nums[i])
backtrack(i+1)
path.pop()
backtrack(0)
return res