Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
The solution set must not contain any duplicate subset, and you may return the subsets in any order.
A subset is any selection of the elements — including the empty selection and the whole array — where each element is used at most as many times as it appears in nums.
n items has 2^n subsets — but duplicate values in nums make some of those subsets identical. How do you keep only one copy of each?nums first. Now every duplicate value sits right next to its twin, so a repeat is always the element just before.if i > start and nums[i] == nums[i-1]: continue.nums[i] is always nums[i-1], so detecting a repeated choice becomes a single neighbor comparison instead of a set lookup.i > start means the duplicate is a sibling choice at the current level — one already tried here. Using i > 0 would also block taking a duplicate deeper in the path (after its twin was already taken), which is exactly how a subset like [2,2] gets built.path is a valid subset at every node, so record it on entry to each call — the empty subset comes from the very first call.path at every node already yields all 2^n unique subsets.used array and skip nums[i] when i > 0 && nums[i] == nums[i-1] && !used[i-1] — the permutation analogue of the same sibling-duplicate rule.n distinct items has exactly 2^n subsets — one per binary number of n bits, which is precisely why the bitmask enumeration works so cleanly.Input: nums = [1,2,2] Output: [[],[1],[1,2],[1,2,2],[2],[2,2]] Even though there are two 2's to choose from, the subset [1,2] is listed only once.
Input: nums = [0] Output: [[],[0]]
- 1 <= nums.length <= 10 - -10 <= nums[i] <= 10
Listing every subset is the classic power-set problem. The twist here is duplicates: an array like [2,2] must yield a single [2], not two identical ones. This tutorial builds from the plain power set up to a backtracking method that never creates a duplicate subset in the first place.
n elements give 2^n subsets.In plain English: choose any collection of the elements (from none of them to all of them), and return the set of all distinct collections. Formally, return the power set of the multiset nums, with no repeated subset.
Worked example — nums = [1,2,2]
nums = [1,2,2] (already sorted) pick nothing -> [] pick 1 -> [1] pick 1, first 2 -> [1,2] pick 1, both 2s -> [1,2,2] pick first 2 -> [2] pick both 2s -> [2,2] picking "1 + second 2" would rebuild [1,2] -> must be skipped answer: [], [1], [1,2], [1,2,2], [2], [2,2]
A few pointed questions before coding show you understand where duplicates cause trouble.
“Can the array contain duplicate values?”
Yes — that is the whole point; a plain power set would emit the same subset more than once.
“Can the values be negative or zero?”
Yes, so a value cannot be used directly as a positive array index.
“Must the empty subset be included?”
Yes — the power set always contains the empty set.
“Does the order of subsets, or of elements within a subset, matter?”
No — any order is accepted, which frees us to sort the input.
“How large can the array get?”
Up to 10 elements, so up to 2^10 subsets — small, meaning the real work is avoiding duplicates, not handling size.
Before I code, a couple of quick checks on the input.
The array can hold duplicates, and I must not return the same subset twice — is that right?
Any order is fine for both the subsets and their contents, so I'll sort first to group equal values together.
After sorting, equal values sit next to each other. So when I stand at index i, a duplicate of nums[i] — if there is one — is exactly nums[i-1]. That turns "have I already tried this value here?" into a single neighbor comparison.
[2,1,2] -> sort -> [1,2,2]
^ ^
equal values now adjacentAt a given recursion depth I decide which value to place next. If I place 2, recurse, come back, and consider 2 again at that same depth, I would rebuild an identical branch. But using the second 2 deeper — after already taking the first — is legitimate; that is how [2,2] is formed. So I skip a duplicate only when it repeats a choice already made at this level: i > start && nums[i] == nums[i-1].
depth 0, start=0: try 1 | try 2 | skip 2 (dup sibling at this level) depth 1 after 2, start=2: try 2 <- allowed, builds [2,2]
In subset backtracking we don't only collect answers at the leaves — the current path is a valid subset at every node. Record it on entry, then extend. This produces all subsets without a separate include/exclude flag per element, and the empty subset falls out of the very first call.
| Brute force (bitmask + set) | Optimal (sorted backtracking) | |
|---|---|---|
| Idea | Enumerate all 2^n masks, dedup with a hash set | Sort, then skip duplicate choices at each level |
| Time | O(n · 2^n) | O(n · 2^n) |
| Space | O(n · 2^n) for the set | O(n) recursion (plus output) |
The full code for both approaches sits in the Approaches selector below.
Key takeaway
To generate distinct combinations from data that contains duplicates, sort first, then at each decision level skip a value equal to the one you just tried: i > start && nums[i] == nums[i-1]. This "skip the sibling duplicate" rule is the reusable heart of Subsets II, Combination Sum II, and Permutations II.
sort(nums)
backtrack(start):
record path as a subset
for i from start to n-1:
if i > start and nums[i] == nums[i-1]: continue # skip dup sibling
path.push(nums[i]); backtrack(i+1); path.pop()