Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Solution. Let’s first talk about the normal Subset problem, which doesn’t has duplicate. There is a loop way rather than recursion. Let’s say [1, 2, 3]. Assume we already have subset(1, 2), which is {[], [1], [2], [1, 2]}.

For 3, we can either add it {[], [1], [2], [1, 2]}

or not add it {[3], [1, 3], [2, 3], [1, 2, 3]}.

So we will have subset(1, 2, 3), which is {[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]}. It’s like for each element, we can either pick up or not pick up it.

For Subsets II problem, let’s say we want to get subset for [1, 2, 3, 3]. Assume we have subset(1, 2) = {[], [1], [2], [1, 2]}. Based on subset(1, 2), we can either add zero 3, add one 3, or two 3 in the subset(1, 2). So the process is like:

public static List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>(Collections.singleton(new ArrayList<>()));
    Arrays.sort(nums);
    int i = 0;
    while (i < nums.length) {
        int next = i + 1;
        while (next < nums.length && nums[next] == nums[i]) {
            next++;
        }
        int size = ans.size();
        for (int j = 0; j < size; j++) {
            List<Integer> curr = new ArrayList<>(ans.get(j));
            for (int k = 1; k <= next - i; k++) {
                curr.add(nums[i]);
                ans.add(new ArrayList<>(curr));
            }
        }
        i = next;
    }
    return ans;
}

Check my code on github.