Subsets II
Subsets II: given an integer array nums that may contain duplicates, return all possible subsets (the power set) without duplicate subsets.
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
Intuition
Subsets ii returns the power set of an array that may contain duplicates, without producing duplicate subsets. The base algorithm is Subsets; the whole problem is the de-duplication.
The naive fix is to generate everything and drop the results into a set. That works but requires making each subset hashable and does wasted work generating duplicates only to discard them. The better approach prevents them from being created at all.
Sorting first is what makes prevention possible, because equal values become adjacent and a repeat can be recognised with a comparison against the previous element.
Then the rule is precise, and stating it exactly is the difference between correct and subtly wrong:
- Within one branching level, skip a value equal to the one just tried; across levels, do not skip.
The condition i > start && nums[i] == nums[i-1] captures that. i > start means "this is not the first choice at this level", so a duplicate is only skipped when a sibling branch already used that value. When a duplicate appears at a deeper level, it is a legitimate second copy inside one subset — [2, 2] must exist — and the i > start guard correctly permits it.
Dropping the i > start half is the classic error. It skips duplicates everywhere, losing every subset that legitimately contains a value twice.
Subsets with duplicates. Sorting makes equal values adjacent, and the guard i > start skips a repeat only when it would start a sibling branch — the same value is still allowed deeper in the path. That distinction between "same depth" and "same path" is the crux of every duplicate-handling backtracking problem.
Approach
Before reading on: price up what the direct approach costs here, then ask what has to be undone after each choice so the next branch starts clean. Aim for O(n·2ⁿ) time and O(n) space.
Start from the plain Subsets walk
Append a copy of the current path at every node, then loop over which later element to add next, recursing and undoing. Every node is a valid subset, which is why no explicit base case is needed.
Sort so duplicates are adjacent
Sorting puts equal values next to each other, letting a repeat be detected by comparing with the immediately preceding element. Without sorting, duplicates are scattered and no local check can find them.
Skip duplicates within a level only
Inside the loop, skip when i > start && nums[i] == nums[i-1]. This says: at this branching point a sibling already tried this value, so trying it again would rebuild an identical subset.
Understand why `i > start` is essential
Dropping it skips duplicates at every depth, which loses subsets that legitimately contain a value twice — [2, 2] would never be generated. The guard permits a repeat at a deeper level while blocking it as a sibling.
Append a copy, not the path
Store a copy of the current list; appending the live list saves a reference that backtracking will mutate, corrupting results already recorded.
Undo after each branch
Pop the element after the recursive call so the next sibling starts from a clean path. Forgetting this leaks elements between branches and produces subsets that were never actually built.
Cost of the enumeration
Up to 2ⁿ subsets each costing O(n) to copy gives O(n · 2ⁿ) time, after an O(n log n) sort. Duplicates reduce the real output below 2ⁿ, which is the point of the skipping rule.
Solution & live demo
Common pitfalls
Skipping with i > 0 instead of i > start
if i > 0 and nums[i] == nums[i - 1]:
continueif i > start and nums[i] == nums[i - 1]:
continuei > 0 also blocks the first candidate of a branch, so [2, 2] can never be built from two equal values. The duplicate must be skipped only when it repeats a choice already tried at this same level.
Forgetting to sort
def subsetsWithDup(self, nums):
res = []nums.sort()
The skip test compares against the immediately preceding element, which only identifies duplicates when equal values are adjacent. On unsorted input duplicates scatter and slip through.
Deduplicating the results afterwards
return [list(x) for x in {tuple(sorted(s)) for s in res}]if i > start and nums[i] == nums[i - 1]: continue
It produces the right answer but generates every duplicate subset first, then pays to hash and discard them. Pruning at the branch stops the work before it happens.
Edge cases
Yields [[], [2], [2,2], [2,2,2]] — each multiplicity once, no repeats.
The skip never triggers; behaves like ordinary Subsets.
Returns [[]] — just the empty subset.