给你一个整数数组 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