90. Subsets II

SubsetsII.java

class Solution {
    
    // https://leetcode.com/problems/subsets-ii/
    // 90. Subsets II

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> output = new LinkedList();
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums);
        rec(nums, output, new ArrayList<>(), 0, used);
        return output;    
    }
    
     public void rec(int[] input, List<List<Integer>> output, List<Integer> temp, int index, boolean[] used) {
        output.add(new ArrayList<>(temp));
        for (int i = index; i < input.length; i++) {
            if (used[i]) continue;
            if (i>0 && input[i] == input[i-1] && !used[i-1]) continue;
            used[i] = true;
            temp.add(input[i]);
            rec(input, output, temp, i+1, used);
            used[i] = false;
            temp.remove(temp.size() - 1);
        }
    }
}