491.递增子序列

题目：. - 力扣（LeetCode）

题解：代码随想录

AC代码：

class Solution {List<List<Integer>> res=new ArrayList<>();List<Integer> path=new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backStracking(nums,0);return res;}public void backStracking(int[] nums,int startIndex){if(path.size()>=2) res.add(new ArrayList<>(path));HashSet<Integer> hs=new HashSet<>();for(int i=startIndex;i<nums.length;i++){if(!path.isEmpty()&&path.get(path.size()-1)>nums[i]||hs.contains(nums[i])) continue;hs.add(nums[i]);path.add(nums[i]);backStracking(nums,i+1);path.removeLast();}}
}

简单说一下思路：

个人认为本题和组合问题（不能有重复的组合那道）有一点点类似，因为都有一个同层不能重复取，而同枝可重复取（参考题解中Carl的思想，把回溯的全过程看成一棵树）

但是要明确的是该题和上面提到的组合问题不同的是，这个题是有顺序要求的不能进行排序，因为我们要求的是该集合中的递增的子序列（要按照原数组的顺序）

然后值得一提的是因为本题目的数据范围不大，我们直接使用了HashMap来进行一个去重操作（要时刻记得这里的去重是同层的，也就是剪枝，把会重复的剪掉，这里有点难理解，我写一下我的思路：举一个好理解的例子，如果没有这个同层去重的操作，我的数组为[7,7]，现在进行回溯的步骤，第一个分支第一层取7第二层取7符合要求得到一个答案[7,7]，第二个分支开始，第一层也是取7，第二层同样是7，和第一个分支就重复了，说明他是没必要再多算的），当然也可以用之前用过的used数组。

---------------------------------------------------------------------------------------------------------------------------------

就这样啦，希望下次能不看题解一次过...