491. 递增子序列

回溯

class Solution {

    List> list = new ArrayList<>();
    LinkedList li = new LinkedList<>();

    public List> findSubsequences(int[] nums) {

        backtracking(nums, 0);
        return list;
    }

    public void backtracking(int[] nums, int startIndex){

        /**
         * 所有个数大于等于2的子集都要收集
         * 注意此处不能return，否则只能收集长度为2的子集
         */
        if (li.size() >= 2) {
            list.add(new ArrayList<>(li));
        }

        /**
         * 要保持原有的递增顺序，不能先将整个数组排序
         * 使用辅助数组，可以将使用过的数字记录下来，在同一层循环中，只要碰到相同的数字，或者数字小于当前列表最后的数字，就直接略过
         */
        LinkedList used = new LinkedList<>();

        for (int i = startIndex; i < nums.length; i++) {

            if (used.contains(nums[i]) || (!li.isEmpty() && nums[i] < li.getLast())) {
                continue;
            }

            /**
             * 注意循环结束后，不能对used数组进行回溯，因为它不是全局变量，只对这一个for循环生效
             */
            li.add(nums[i]);
            used.add(nums[i]);
            backtracking(nums, i + 1);
            li.removeLast();
        }
    }
}

/**
 * 时间复杂度 O(n×2^n)
 * 空间复杂度 O(n)
 */

https://leetcode-cn.com/problems/increasing-subsequences/