74.Subsets II
Problem
Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
The result must not contain duplicate subsets. [1,2] built from the first 2 and [1,2] built from the second 2 are the same subset and must appear only once. Subsets may be returned in any order.
Examples
Input: nums = [1, 2, 2]
Output: [[], [1], [1,2], [1,2,2], [2], [2,2]]
Explanation: Plain Subsets would produce [2] and [1,2] twice; they appear once here.Input: nums = [0]
Output: [[], [0]]Constraints
1 <= nums.length <= 10-10 <= nums[i] <= 10
💡 Key Insight
Sort so equal values sit together. Then duplicates only arise when, at the same level of the decision tree, you start a branch with a value equal to the one you just tried. The rule "at a given level, skip nums[i] if i > start and nums[i] == nums[i - 1]" keeps exactly one branch per distinct value per level — and still allows [2,2] because the second 2 is chosen at a deeper level.
Brute Force with a Set
TimeO(n · 2^n)SpaceO(n · 2^n)Intuition
Generate all 2^n subsets as in Subsets, but sort first so equal multisets produce identical lists ([1,2] never appears as [2,1]). Then a HashSet<List<Integer>> removes duplicates automatically.
Algorithm
- Sort
nums. - For each
maskin0 .. 2^n - 1, build the subset of chosen indices (in increasing order). - Add it to a
Set<List<Integer>>. - Return the set as a list.
Visualization
nums sorted = [1,2,2]
mask 010 -> [2] new
mask 100 -> [2] already in set, ignored
mask 011 -> [1,2] new
mask 101 -> [1,2] already in set, ignored
mask 110 -> [2,2] newCode
import java.util.*;
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums); // equal subsets now produce identical lists
int n = nums.length;
Set<List<Integer>> seen = new HashSet<>();
for (int mask = 0; mask < (1 << n); mask++) {
List<Integer> subset = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (((mask >> i) & 1) == 1) subset.add(nums[i]);
}
seen.add(subset); // duplicates are dropped by the set
}
return new ArrayList<>(seen);
}
}Complexity
- Time: O(n · 2^n) — every mask is built and hashed in O(n).
- Space: O(n · 2^n) — the set stores every distinct subset.
Iterative with Duplicate Handling
TimeO(n · 2^n)SpaceO(n) extra besides the output.Intuition
Use the cascading idea from Subsets. For a new value, append it to every existing subset. For a value equal to the previous one, appending to the old subsets would recreate subsets we already have — so append only to the subsets created in the previous round (those that already contain the previous copy).
Algorithm
- Sort
nums;result = [[]];prevStart = 0. - For each index
i:start = (i > 0 && nums[i] == nums[i-1]) ? prevStart : 0.size = result.size();prevStart = size.- For
jfromstarttosize - 1: copyresult[j], appendnums[i], add.
- Return
result.
Visualization
nums = [1,2,2]
i=0 (1) : [[]] -> + [1] result: [], [1]
i=1 (2, new) : extend all 2 -> [2], [1,2] result: [], [1], [2], [1,2]
i=2 (2, repeat) : extend only last round [2],[1,2]
-> [2,2], [1,2,2] result has 6 subsetsCode
import java.util.*;
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<>());
int prevStart = 0;
for (int i = 0; i < nums.length; i++) {
// a repeated value only extends subsets made in the previous round
int start = (i > 0 && nums[i] == nums[i - 1]) ? prevStart : 0;
int size = result.size();
prevStart = size;
for (int j = start; j < size; j++) {
List<Integer> copy = new ArrayList<>(result.get(j));
copy.add(nums[i]);
result.add(copy);
}
}
return result;
}
}Complexity
- Time: O(n · 2^n) — at most
2^nsubsets, each copied in O(n). - Space: O(n) extra besides the output.
Backtracking with SkipOptimal
TimeO(n · 2^n)SpaceO(n)Intuition
Every node of the recursion tree is a subset (record it on entry). From node start, try each nums[i] for i >= start as the next element. Since nums is sorted, two equal values at the same level would produce identical subtrees, so skip nums[i] when i > start && nums[i] == nums[i - 1].
Algorithm
- Sort
nums. backtrack(start):- Record a copy of
path. - For
ifromstartton - 1:- If
i > startandnums[i] == nums[i - 1], continue. - Push
nums[i],backtrack(i + 1), pop.
- If
- Record a copy of
Visualization
flowchart TD
R["[] start=0"] -->|"1"| A["[1]"]
R -->|"2 at i=1"| B["[2]"]
R -.->|"2 at i=2 skip"| X["duplicate branch"]
A -->|"2 at i=1"| A1["[1,2]"]
A -.->|"2 at i=2 skip"| X2["duplicate branch"]
A1 -->|"2 at i=2"| A11["[1,2,2]"]
B -->|"2 at i=2"| B1["[2,2]"]Code
import java.util.*;
class Solution {
private final List<List<Integer>> result = new ArrayList<>();
private final List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums); // group equal values together
backtrack(nums, 0);
return result;
}
private void backtrack(int[] nums, int start) {
result.add(new ArrayList<>(path)); // every node is a valid subset
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) {
continue; // same value already tried at this level
}
path.add(nums[i]);
backtrack(nums, i + 1);
path.remove(path.size() - 1);
}
}
}Complexity
- Time: O(n · 2^n) — at most
2^nsubsets, each copied in O(n); sorting is O(n log n). - Space: O(n) — recursion depth and
path(output excluded).
Complexity Comparison
| Approach | Time | Space (extra) |
|---|---|---|
| Brute Force + Set | O(n · 2^n) | O(n · 2^n) |
| Iterative | O(n · 2^n) | O(n) |
| Backtracking with Skip | O(n · 2^n) | O(n) |
Common Pitfalls
- Forgetting to sort — the skip rule only works when duplicates are adjacent, and the set approach needs a canonical order.
- Writing
i > 0instead ofi > startin the skip check — that wrongly forbids[2,2]by skipping the second2at a deeper level. - Using a set without sorting:
[1,2]and[2,1]would be treated as different lists. - Adding
pathitself rather than a copy.