Leetcode 491 递增子序列

题意理解：

输入：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.

? ?要注意：集合中的元素有重复，需要去重操作。——这就是这道题的难点。

解题思路：

? ? ? ? 涉及子集问题，一般可以用回溯的方法来进行解决。

? ? ? ? 回溯的解决方案通常可以抽象为一棵树。可以画一幅画来理解：

????????紫色的部分即为需要剪枝去重的地方，所以我们需要一个设置uset来记录当前层用过的元素，当当前层有重复元素出现时，需要进行剪枝操作。

????????

1.暴力回溯+剪枝优化

?回溯算法三个常见步骤：

? ? ? ? 确定返回值和参数列表

? ? ? ? 确定终止条件：集合中所有元素遍历完，即startIndex>nums.size

? ? ? ? 确定单层逻辑：使用uset来记录当前层用过的值。

注意： 子集递增，单不是严格递增，所以允许重复值存在。

? ? ? ? ? ? 剪枝： 当前层当前树枝的重复值要剪枝。

? ? ? ? ? ? ? ? ? ? ? ? 递减子序列要剪枝。

List<List<Integer>> result=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums,0);
        return result;
    }
    public void backtracking(int[] nums,int startIndex){
        //结果收集
        if(path.size()>=2) result.add(new ArrayList<>(path));
        if(startIndex>=nums.length) return;//可以省略，因为startIndex>=nums.length，下面循环不会进入
        //记录当前树枝当前层用过的值
        Set<Integer> uset=new HashSet<>();
        for(int i=startIndex;i<nums.length;i++){
            if(uset.contains(nums[i])){//当前树枝当前层树枝重复则剪枝
                continue;
            }
            if(path.size()!=0&&nums[i]< path.getLast()) continue;//递减时剪枝
            uset.add(nums[i]);
            path.add(nums[i]);
            backtracking(nums,i+1);
            path.removeLast();
        }
    }

2.分析

时间复杂度：O()

空间复杂度：O(n)