090.Subsets II

Posted on | In

Solution 1: accepted 3ms

DFS. Follow-up of 078 Subset. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        subsetsHelper(result, list, nums, 0);
        return result;
    }
    
    public void subsetsHelper(List<List<Integer>> result,
                              List<Integer> list,
                              int[] nums,
                              int pos) {
        result.add(new ArrayList<Integer>(list));
        for (int i = pos; i < nums.length; i++) {
            if (i == pos || nums[i] != nums[i - 1]) { // only remove duplicates in this level, i.e. [1,2] and [1,2]
                list.add(nums[i]);
                subsetsHelper(result, list, nums, i + 1); // will reset duplicates, so we will still have [1, 2, 2]
                list.remove(list.size() - 1);
            } 
        }
    }
}