Subsets II
Given an integer array nums that may contain duplicates, return all possible subsets (the power set) without duplicate subsets.
Intuition
Subsets is a take/skip walk over the decision tree. With duplicates, sort first so equal values sit together, then within one recursion level skip a value identical to the one just tried — that prevents building the same subset 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
Start from the plain Subsets walk
Without duplicates, every node on a backtracking path is a valid subset: append a copy of the current path, then for each later index choose it, recurse, and pop. That generates all 2ⁿ subsets. The problem is that duplicates in the input would make some of those subsets identical.
Sort so duplicates are adjacent
Sort nums first. Now equal values are neighbors, which lets you detect a repeat with a simple nums[i] == nums[i-1] check during the loop.
Skip duplicates within a level
Inside the for-loop, if i > start and nums[i] == nums[i-1], continue — skip it. This says: at this branching point we've already explored a subtree starting with this value, so starting another with the same value would duplicate subsets. The i > start guard still allows the value to be used (just not re-started at the same level), so [1,2,2] style subsets are kept exactly once.
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.