491. 递增子序列

文章目录

491. 递增子序列
思路
回溯三部曲
总结

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

思路

这个递增子序列比较像是取有序的子集。而且本题也要求不能有相同的递增子序列。

这又是子集，又是去重，是不是不由自主的想起了刚刚讲过的90.子集II

就是因为太像了，更要注意差别所在，要不就掉坑里了！

在90.子集II中我们是通过排序，再加一个标记数组来达到去重的目的。

而本题求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了。

所以不能使用之前的排序+used切片标记同层相同元素是否使用过的方式处理去重逻辑!!！

本题给出的示例，还是一个有序数组 [4, 6, 7, 7]，这更容易误导大家按照排序的思路去做了。

为了有鲜明的对比，我用[4, 7, 6, 7]这个数组来举例，抽象为树形结构如图：

在这里插入图片描述

回溯三部曲

1.递归函数参数
本题求子序列，很明显所给列表中一个元素不能重复使用，所以需要startIndex，用于调整下一层递归的起始位置。

代码如下：

func backtracking(nums []int,res *[][]int,path *[]int,startIndex int) {}

2.终止条件
本题其实类似求子集问题，也是要遍历树形结构找每一个节点，所以和回溯算法：求子集问题！一样，可以不加终止条件，startIndex每次都会加1，并不会无限递归。

但本题收集结果有所不同，题目要求递增子序列大小至少为2，所以代码如下：

if len(*path) >= 2 {*res = append(*res,append([]int(nil),*path...))   // 注意这里不要加return，因为要取树上的所有节点,所以还要继续往下取}

3.单层搜索逻辑
在这里插入图片描述

从图中可以看出，同一父节点下的同层上使用过的元素就不能再使用了

那么单层搜索代码如下：

// 每一层都有自己的一个set，使用set来对本层元素进行去重set := make(map[int]bool)for i := startIndex;i < len(nums);i++ {// 当前数字在本层已经用过了，不要再用了，故continue，去重if  set[nums[i]] {continue}if len(*path) > 0 && nums[i] < (*path)[len(*path) - 1] {continue}set[nums[i]] = true // 记录这个元素在本层用过了，本层后面不能再用了*path = append(*path,nums[i])backtracking(nums,res,path,i + 1)*path = (*path)[0:len(*path) - 1]}

对于已经习惯写回溯的同学，看到递归函数上面的set[nums[i]] = true，下面却没有对应的set[nums[i]] = false回溯之类的操作，应该很不习惯吧

这也是需要注意的点，set是记录本层元素是否重复使用，新的一层set都会重新定义，所以要知道set只负责本层！

深入理解对比一下：

排序后 + used切片标记去重的代码，因为切片是排序过的，同层当前要选的数字和之前的相同，但是前面的那个数字还没有标记过，说明是同层重复使用某个数字了，要去重，且used维护的是全局某个数字是否用过，不是特定某层的，所以used切片需要回溯

for i := startIndex;i < len(candidates) && target - candidates[i] >= 0;i++ {if i > 0 && candidates[i] == candidates[i - 1]  && !used[i - 1]{// 同层横向遍历，前一个相同数字没有用过就用后一个数字，是重复的，要去重continue}*path = append(*path,candidates[i])used[i] = truebacktracking(candidates,target - candidates[i],res,path,i+1,used)*path = (*path)[0:len(*path) - 1]used[i] = false
}

用set去重的代码，因为每层都是各自维护同层之前某个相同的数字是否使用过，用过就表示当前同层再选这个元素就重复使用了，要去重，且set不用回溯，因为它本身就是想标记该层某个元素是否用过了。

// 每一层都有自己的一个set，使用set来对本层元素进行去重
set := make(map[int]bool)
for i := startIndex;i < len(nums);i++ {// 当前数字在本层已经用过了，不要再用了，故continue，去重if  set[nums[i]] {continue}if len(*path) > 0 && nums[i] < (*path)[len(*path) - 1] {continue}set[nums[i]] = true // 记录这个元素在本层用过了，本层后面不能再用了*path = append(*path,nums[i])backtracking(nums,res,path,i + 1)*path = (*path)[0:len(*path) - 1]
}

最后整体Go代码如下：

func findSubsequences(nums []int) [][]int {// 选择下一个元素时，需要判断是否大于已选路径中最后添加的元素（它最大）// 由于每个子集不能改变在原数组中的相对顺序，所以没法用排序+used切片辅助去重（因为used需要用到i-1下标）// 因此我们用下Set记录同层某个元素是否已经用过,每层都维护各自的Setif len(nums) == 0 {return nil}res := make([][]int,0)path := make([]int,0)backtracking(nums,&res,&path,0)return res
}func backtracking(nums []int,res *[][]int,path *[]int,startIndex int) {if len(*path) >= 2 {*res = append(*res,append([]int(nil),*path...))  // 注意这里不要加return，因为要取树上的所有节点,所以还要继续往下取 }// 每一层都有自己的一个set，使用set来对本层元素进行去重set := make(map[int]bool)for i := startIndex;i < len(nums);i++ {// 当前数字在本层已经用过了，不要再用了，故continue，去重if  set[nums[i]] {continue}if len(*path) > 0 && nums[i] < (*path)[len(*path) - 1] {continue}set[nums[i]] = true // 记录这个元素在本层用过了，本层后面不能再用了*path = append(*path,nums[i])backtracking(nums,res,path,i + 1)*path = (*path)[0:len(*path) - 1]}
}