LeetCode491. 递增子序列【JAVA教程】

思路

首先该题是求递增子序列，那么就不能对数组进行排序。可以看下代码随想录的题解

 可以从上图看到每一层的元素不可以重复，而且原数组不能排序。所以就只能没一层插入一个元素就记录一个元素，到下一层循环的时候该层的记录就清空。这就是为什么要把userd数组在for循环上重新new一个的原因。

代码

class Solution {
    List path = new ArrayList();
    List<List> res = new ArrayList();
    public List<List> findSubsequences(int[] nums) {
        back(nums,0);
        return res;
    }
    public void back(int[] nums,int startIndex){
        if(path.size()>=2 && path.size() nums.length){
            return;
        }
        int[] used = new int[201];
        for(int i = startIndex;i<nums.length;i++){
            if(!path.isEmpty() && nums[i] <path.get(path.size()-1) || used[nums[i]+100] == 1){
                continue;
            }
            path.add(nums[i]);
            used[nums[i] + 100] = 1;
            back(nums,i+1);
            path.remove(path.size()-1);
        }
    }
}