491. Increasing Subsequences

Link

Solution

典型的backtracking problem, only thing we need to take care is dupplicated number cause duplicated conbination:

ex : [6,7,7] -> induce [6] [7] [7], [6,7], [6,7]

We used a set to recored if the number is used before.

  public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> ret = new LinkedList<>();
        helper(nums, 0, new LinkedList<Integer>(), ret);
        return ret;
    }
    
    public void helper(int[] nums, int start, List<Integer> temp, List<List<Integer>> ret){
        if(temp.size() >= 2){
            ret.add(new LinkedList<Integer>(temp));
        }
        Set<Integer> used = new HashSet<>();
        for(int i = start; i < nums.length; i++){
            if(used.contains(nums[i])) continue;
            if(temp.size() == 0 || temp.get(temp.size()-1) <= nums[i]){
                temp.add(nums[i]);
                used.add(nums[i]);
                helper(nums, i+1, temp, ret);
                temp.remove(temp.size()-1);
            }
            
        }
    }