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.
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Input: nums = [0]
Output: [[],[0]]
Similar to Subsets I, but now we have duplicates to handle.
Problem: [1,2,2] could generate [1,2] twice if we're not careful.
Solution:
Example: After choosing first 2, skip the second 2 at the same level.
This is a Backtracking with Duplicate Handling problem:
def backtrack(start, current):
result.append(current.copy())
for i in range(start, len(nums)):
# Skip duplicates at same level
if i > start and nums[i] == nums[i-1]:
continue
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
Key: i > start ensures we only skip duplicates at same recursion level, not different levels.
Time: O(n × 2^n)
Space: O(n) recursion depth
1import java.util.*;
2
3class Solution {
4 public List<List<Integer>> subsetsWithDup(int[] nums) {
5 List<List<Integer>> result = new ArrayList<>();
6 Arrays.sort(nums); // Sort to group duplicates
7 backtrack(0, nums, new ArrayList<>(), result);
8 return result;
9 }
10
11 private void backtrack(int start, int[] nums, List<Integer> current, List<List<Integer>> result) {
12 result.add(new ArrayList<>(current));
13
14 for (int i = start; i < nums.length; i++) {
15 // Skip duplicates at same recursion level
16 if (i > start && nums[i] == nums[i - 1]) {
17 continue;
18 }
19
20 current.add(nums[i]);
21 backtrack(i + 1, nums, current, result);
22 current.remove(current.size() - 1);
23 }
24 }
25}
26