Problem

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Examples

Example 1:

Input:
nums = [1,2,2]
Output:
 [ [],[1],[1,2],[1,2,2],[2],[2,2] ]

Example 2:

Input:
nums = [0]
Output:
 [ [],[0] ]

This is follow up from: Subsets Problem

Solution

Method 1 - Backtracking

In this case we have to sort the array, as it is easy to compare if elements are duplicate by just looking at adjacent places.

Thought Process 1 - Focus One Element at Each Level

Each recursion level focuses on one element, we need to decide choose or not choose this element. (Every level split into 2 branches.)

public List<List<Integer>> subsetsWithDup(int[] nums) {
	Arrays.sort(nums);
	List<List<Integer>> ans = new ArrayList<>();

	dfs(nums, 0, ans, new ArrayList<>());

	return ans;
}

public void dfs(int[] nums, int idx, List<List<Integer>> ans, List<Integer> subAns) {
	if (idx >= nums.length){
		ans.add(new ArrayList<>(subAns));
		return;
	}

	// include the number in the set
	subAns.add(nums[idx]);
	dfs(nums, idx+1, ans, subAns);

	// don't include the number in the set
	subAns.remove(subAns.size() - 1);
	//we will not add all the following same element, just jump to the index where nums[index] is a different value
	int i = idx;
	while(i < nums.length && nums[i] == nums[index]){
		i++;
	} 
	dfs(nums, i, ans, subAns);
}

another flavour is use flag choosePre:

public List < List<Integer>> subsetsWithDup(int[] nums) {
	Arrays.sort(nums);
	List < List<Integer>> ans = new ArrayList<>();
	helper(nums, 0, false, ans, new ArrayList<>());
	return ans;
}


public void helper(int[] nums, int pos, boolean choosePre, List < List<Integer>> ans, List<Integer> subAns) {
	if (pos == nums.length) {
		ans.add(new ArrayList<>(subAns));
		return;
	}

	helper(nums, idx + 1, false, ans, subAns);

	if (idx >= 1 && nums[idx] == nums[idx - 1] && !choosePre) return;
	
	subAns.add(nums[idx]);
	helper(nums, idx + 1, true, ans, subAns);
	subAns.remove(subAns.size() - 1);
}

Thought Process 2 - Focus on All the Following Elements at Each Level

Each recursion level focuses on all the following elements. We scan through all the following elements and decide whether to choose or not choose that element. (Every level split into N branches.)

public List<List<Integer>> subsetsWithDup(int[] nums) {
	Arrays.sort(nums);
	List<List<Integer>> ans = new ArrayList<>();
	helper(nums, 0, ans, new ArrayList<>());
	return res;
}

public void helper(int[] nums, int idx, List<List<Integer>> ans, List<Integer> subAns) {
	ans.add(new ArrayList<>(subAns));
	for (int i = idx; i<nums.length; i++) {
		if (i > idx && nums[i] == nums[i - 1]) continue;
		subAns.add(nums[i]);
		helper(nums, i + 1, ans, ls);
		subAns.remove(ls.size() - 1);
	}
}

Method 2 - Iterative

If we want to insert an element which is a dup, we can only insert it after the newly inserted elements from last step.

public List<List<Integer>> subsetsWithDup(int[] nums) {
  Arrays.sort(nums);
  List<List<Integer>> ans = new ArrayList<>();
  ans.add(new ArrayList<Integer>());

  int size = 0, startIndex;
  for(int i = 0; i < nums.length; i++) {
    startIndex = (i >= 1 && nums[i] == nums[i - 1]) ? size : 0;
    size = ans.size();
    for(int j = startIndex; j < size; j++) {
      List<Integer> temp = new ArrayList<>(ans.get(j));
      temp.add(nums[i]);
      ans.add(temp);
    }
  }
  return ans;
}