🔥个人主页：代码不加冰（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：LeetCode刷题日记 ， 苍穹外卖日记，SSM框架深入，JavaWeb，
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！
前言：
大家好我是代码不加冰，这周过完就正式进入痛苦的期末周了，文章平时也没什么时间写，只能每天抽出一点时间刷几题算法和看看八股，没事的时候还是用cc跑了几个项目，然后跑了个自用的时间管理软件，还是挺好玩的，废话不多说，进入到我们的今日刷题环节！
摘要：
题目背景：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
题目解析：
首先题目要求：
给定一个整数数组
nums，找出所有不同的递增子序列（长度至少为2）。这里的递增指的是：
nums[i] <= nums[j]注意：
- 不是连续子数组
- 是子序列，可以跳过元素
- 结果不能有重复序列
- 但是数组中可以有重复的元素
我们一眼看出来是回溯类型的题目，和我们前面做的子集问题类似，但是去重的思路不一样。
本质区别总结
力扣90：子集
可以排序 排序后： 重复元素连续 树层去重： if(i > startIndex && nums[i] == nums[i-1]) 利用排序去重本题
不能排序 重复元素可能分散 树层去重： HashSet<Integer> used 记录本层已经使用过的数字可以这样记：
| 题目 | 是否排序 | 去重方式 |
|---|---|---|
| 90 子集Ⅱ | 可以 | nums[i]==nums[i-1] |
| 40 组合总和Ⅱ | 可以 | nums[i]==nums[i-1] |
| 47 全排列Ⅱ | 可以 | nums[i]==nums[i-1] + used[] |
| 491 递增子序列 | 不能 | HashSet树层去重 |
所以，这道题目不能排序，题目要的是递增的子序列，如果对原来的数组进行排序，结果就完全不一样了，
例如
{1，3，5，4}
结果：[1,3],[1,5],[1,4],[3,5],[3,4],[1,3,5],[1,3,4]
{5，3，4，1}
结果：[[3,4]]
这两个的结果完全不一样。
回溯三部曲
参数
需要知道：
当前遍历到哪里 当前路径因此：
backtracking(nums,startIndex)
终止条件
题目要求：
长度 >= 2所以：
path.size() >= 2就加入结果集。注意：这里不能 return。因为后面可能还能继续选。
例如：
[4,6]还能扩展成：
[4,6,7]所以：
if(path.size() >= 2){ result.add(...) }继续向下搜索。
单层搜索逻辑
遍历当前位置后面的所有元素：
for(int i=startIndex;i<nums.length;i++)
如何保证递增
当前数字：
nums[i]要大于等于路径最后一个数字：
nums[i] >= path最后一个元素否则跳过：
if(!path.isEmpty() && nums[i] < path.get(path.size()-1)) { continue; }
本题最大难点：去重
看看这个例子：
[4,6,7,7]假设第一层：
4 6 7 7如果两个 7 都选：
[4,7]会出现两次。因此：
同一树层不能出现相同数字同一树枝可以例如：
[7,7]是合法答案。
树层去重
使用 HashSet
每一层创建一个：
HashSet<Integer> used = new HashSet<>();如果本层已经出现：
used.contains(nums[i])直接跳过：
if(used.contains(nums[i])){ continue; }然后记录：
used.add(nums[i]);
为什么不能全局 HashSet
例如：
[7,7]第一个7用了。
第二个7如果全局去重：
直接被过滤结果：
[7,7]永远出不来。所以：
只能树层去重 不能全局去重这是本题核心。
我们可能会想：
if(i > startIndex && nums[i] == nums[i - 1]){ continue; }90子集之所以能用
if(i > startIndex && nums[i] == nums[i - 1])是因为题目允许先排序，排序后相同元素一定挨在一起，所以只要发现当前元素和前一个元素相同，就说明这是同一层的重复选择，可以直接跳过。
而力扣491要求求递增子序列，必须保持原数组的相对顺序，不能排序，相同元素可能分散在数组的不同位置，例如[4,7,6,7]中两个7中间隔着一个6，此时nums[i] == nums[i-1]根本检测不到重复，因此90题的去重方式失效。491只能使用HashSet记录当前树层已经使用过的数字，只要这一层出现过某个数字，后面再遇到相同数字就跳过，从而实现树层去重。
简单来说：90是利用排序后“相同元素连续”的特性去重，491是利用HashSet记录“当前层出现过哪些值”去重。
题目答案：
class Solution { List<List<Integer>> result = new ArrayList<>(); LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); backtracking(nums, 0); return result; } private void backtracking(int[] nums, int startIndex) { result.add(new ArrayList<>(path)); for (int i = startIndex; i < nums.length; i++) { // 树层去重 if (i > startIndex && nums[i] == nums[i - 1]) { continue; } path.add(nums[i]); backtracking(nums, i + 1); path.removeLast(); } } }结语：
如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！
