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数组。

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

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