Problem statement
Return all distinct subsets of an array that can contain duplicate values. Include the empty subset. For [1,2,2], [2,2] is valid, but [2] must appear only once.
The published LeetCode bounds allow 1–10 elements from −10 to 10. Output order is arbitrary. Negative values do not change the algorithm because it uses positions and equality, not sum pruning.
Constraints & requirements
- CONTRACT
- Verified bounds: 1–10 elements, values −10–10. Equal elements can both appear in a subset, but duplicate copies of the same subset must not appear. Input remains unchanged.
Examples 3 test cases
Example 1 Case 1
- Input
[1,2,2]- Output
[[],[1],[1,2],[1,2,2],[2],[2,2]]
Keep [2,2], but emit [2] only once.
Example 2 Case 2
- Input
[0]- Output
[[],[0]]
A zero-valued singleton differs from the empty subset.
Example 3 Case 3
- Input
[2,2]- Output
[[],[2],[2,2]]
Choosing zero, one or two copies gives three unique subsets.
Hints Optional
01Hint 1
Every prefix is already an answer; there is no target to wait for.
02Hint 2
Sort a copy, then skip equal next choices at the same level.
03Hint 3
Allow duplicates deeper in the path by testing i>start, not i>0.
How to think before coding
Every current prefix is a valid subset, so save it at entry, not only at a fixed leaf depth. The call’s start index prevents reusing a position. After sorting, skip equal nums[i] only when i>start; a repeated value at a deeper level may form [2,2] and is legal. Save a list copy, recurse at i+1, and remove the last chosen value.
Brute force and the improvement
Generate all 2^n index subsets, sort each value list or sort the input copy first, and deduplicate complete lists in a set. Selection/copy work takes O(n·2^n); the set may retain O(n·2^n) values in the all-distinct worst case. Sorting a copy and skipping equal choices at the SAME depth prevents duplicates before building them. Output remains exponential when all inputs differ; the benefit is avoiding duplicate subtrees when equal values occur.
Intuition: save every valid prefix
Unlike Combination Sum II, there is no target condition. [], [1] and [1,2] are all complete answers, even if we can extend them. Save a copy as soon as a recursive call starts.
Sorting brings duplicate values together. At the root, the first 2 can begin [2]; starting again with the second 2 would repeat the same value list. Skip that equivalent sibling. Deeper in the first 2 branch, the second 2 is still available and creates [2,2].
Think “skip equivalent next choices,” not “ban repeated numbers.” That is why removing duplicates from the input is wrong.
Algorithm
- Sort a copy of the array.
- Save a copy of the current path, including the initial empty path.
- Try the next position from start onward.
- Skip it when it equals the previous value and i is greater than this call’s start.
- Append, recurse from i+1, then undo the append.
Java solution
Sort a copy, save a path copy at entry, skip duplicate sibling choices and recurse from the next index. These operations preserve repeated values inside a legitimate subset.
import java.util.*;
class Solution {
public static List<List<Integer>> subsetsWithDup(int[] nums) {
int[] sorted = nums.clone(); // Sorting a copy avoids changing the input.
Arrays.sort(sorted); // Equal values must be adjacent for sibling duplicate skipping.
List<List<Integer>> result = new ArrayList<>();
uniqueSubsets(sorted, 0, new ArrayList<>(), result);
return result;
}
private static void uniqueSubsets(int[] nums, int start,
List<Integer> path, List<List<Integer>> result) {
result.add(new ArrayList<>(path)); // EVERY prefix is a subset, including the empty one.
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) continue; // Equal values at this level make duplicates.
path.add(nums[i]); // A deeper copy of the same value is still allowed.
uniqueSubsets(nums, i + 1, path, result); // Use each array position at most once.
path.remove(path.size() - 1); // Undo for the next sibling; saved copies do not change.
}
}
public static void main(String[] args) {
System.out.println(subsetsWithDup(new int[]{1, 2, 2})); // [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
}
}The default invocation returns [[],[1],[1,2],[1,2,2],[2],[2,2]]. Copies in the result survive subsequent backtracking.
Recursion tree and dry run

Read the text transcript
Follow the Java, step by step
Example: nums = [1,2,2]
What to track: Track start and path. Every entered call saves its prefix. Equal siblings are skipped, but the second 2 remains available in a deeper call.
-
Save the empty prefix
Java operationresult.add(new ArrayList<>(path));Statestart = 0; path = []; result = [[]]Unlike target-sum enumeration, every prefix is an answer, including the root.
-
Choose 1 and then the first 2
Java operationuniqueSubsets(nums, i + 1, path, result);Stateentered prefixes: [1] at start = 1, then [1,2] at start = 2Each entered call saves a copy before exploring its remaining positions.
-
Allow the deeper equal value
Java operationif (i > start && nums[i] == nums[i - 1]) continue;Statestart = 2; i = 2; equality exists but i > start is false; save [1,2,2]This second 2 extends the first 2; it is not a duplicate sibling branch.
-
Undo before the sibling check
Java operationpath.remove(path.size() - 1);Statereturn restores [1,2], then [1]; the start = 1 frame resumes with i = 2Now i > start and the equal previous 2 make this sibling a duplicate, so it is skipped.
-
Explore the root’s first 2
Java operationuniqueSubsets(nums, i + 1, path, result);Stateroot chooses index 1: save [2]; its child chooses index 2: save [2,2]These prefixes do not contain 1, so they are new subsets.
-
Finish the root
Java operationif (i > start && nums[i] == nums[i - 1]) continue;Stateroot i = 2 is skipped; path = []; six saved snapshots remainA second root-level [2] branch would duplicate the previous root branch. Saved copies survive every undo.
Final result: [[],[1],[1,2],[1,2,2],[2],[2,2]]
[] → save ├─ choose 1: [1] → save │ ├─ choose first 2: [1,2] → save │ │ └─ choose second 2: [1,2,2] → save │ └─ second 2 as sibling → skip ├─ choose first 2: [2] → save │ └─ choose second 2: [2,2] → save └─ second 2 as root sibling → skip
| Before choice | Action | After returning and undoing |
|---|---|---|
| [] | Add 1 and explore | [] |
| [1] | Add first 2 and explore | [1] |
| [1,2] | Add second 2 and save | [1,2] |
| [] | Add first 2 and explore | [] |
The call stack pop and path removal are different events: first the child finishes, then the resumed parent removes its temporary choice.
Why it works
The path follows increasing input indices, so no position is selected twice. Every valid subset has a sorted value representation. At each level, choosing the first available occurrence of its next value leaves the remaining copies available below it. Equivalent later sibling occurrences add nothing new. Consequently all distinct value subsets appear once.
Complexity and alternative approaches
Worst-case time is O(N·2^N), including subset copies, plus O(N log N) sorting. With all distinct values, every subset is produced. Auxiliary space is O(N), including the input copy, path and stack; output can take O(N·2^N).
If value groups have counts c₁, c₂, …, the number of distinct subsets is U = ∏(cᵢ+1): choose zero through cᵢ copies of each value. The total size of those U returned lists describes output cost more precisely than only counting them.
Alternatives include generating all index subsets and deduplicating canonical lists, or branching by how many copies of each value group to take. The sibling-skip version avoids an output-sized deduplication set.
Common mistakes
- Forgetting the empty subset.
- Testing
i > 0, which incorrectly skips repeated values in deeper calls. - Using a global visited-value set, which loses
[2,2]. - Saving the shared path object instead of a copy.
- Waiting until index reaches the end without designing an include/skip tree; the loop-prefix method saves at entry.