491. 非递减子序列

一 题目：

二 思路：

涉及到一个位置数据放不放置会影响后续结果，我们都采用回溯的方法
本题目难在去冲，同一个位置我们需要保障一个数只放一次，那么这里我们用的是Set去冲，让一个数只放一次，比如刚进循环的时候curIndex=0，这时候我们其实放的是cur第一位置的数，这个位置同一个数只放一次，后面进到后面循环就是其他位次的数了，注意这里curIndex不同于cur放的第几个数哦，仅代表从curIndex位置开始选新的数

三 代码：

    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        if (nums.length < 2) {
            return res;
        }

        search(new LinkedList<>(), nums, 0);
        return res;
    }

    private void search(LinkedList<Integer> cur, int[] nums, int curIndex) {
        //没加一个数据后的新链一定都是不一样的
        if (cur.size() >= 2) {
            res.add(new ArrayList<>(cur));
        }

        if (curIndex >= nums.length) {
            return;
        }

        //从curIndex安排新加入数据
        //同一位置已安置过的数据
        Set<Integer> set = new HashSet<>();
        for (int i = curIndex; i < nums.length; i++) {
            // 1. 如果 set 中已经有与 nums[i] 相同的值了，说明加上 nums[i] 后的所有可能的递增序列之前已经被搜过一遍了，因此停止继续搜索。
            if (set.contains(nums[i])) {
                continue;
            }  else {
                //2.set中没有与 nums[i] 相同的值
                set.add(nums[i]);

                //如果满足放进去的条件就放试试，放完就移除继续后面算不放，不需要单独写不放
                if (cur.isEmpty() || nums[i] >= cur.getLast()) {
                    cur.add(nums[i]);
                    search(cur, nums, i + 1);
                    cur.removeLast();
                }
            }
        }
    }