🌕 🌕 491. 递增子序列

难度: 🌕 🌕

问题描述

---

解法

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        // 思路：
        // 重复数组 & 非严格递增子序列(len >= 2)
        // 由于此次不可改变数组相对顺序，因此不可利用 nums[i] == nums[i - 1] 去重
        int len = nums.length;
        LinkedList<Integer> path = new LinkedList<>();
        mySol(nums, len, 0, path);
        return res;
    }

    private void mySol(int[] nums, int len, int index, LinkedList<Integer> path) {
        // 递归终止条件
        if(index > len) {
            return;
        }
        if(path.size() >= 2) {
            res.add(new LinkedList<>(path));
        }
        // 单层去重，加在这里
        HashSet<Integer> set = new HashSet<>();
        for(int i = index; i < len; i ++) {
            if(!path.isEmpty() && nums[i] < path.peekLast()) {
                continue; // 不满足非严格递增条件
            }
            if(set.contains(nums[i])) {
                continue; // 前面已经去过该情况
            }
            path.addLast(nums[i]);
            set.add(nums[i]);
            mySol(nums, len, i + 1, path);
            path.removeLast();
        }
    }
}

---

输出