Core Insight Build one partial answer at a time and undo each choice so sibling branches start clean.
Common Pitfall Copy a completed path before appending it to results; later mutations must not alter it.
Description
Return all subsets, handling duplicates.
Constraints
- Time Complexity:
O(n·2^n) - Space Complexity:
O(n)
Tags
arraybacktrackingbit-manipulation
Implementation Plan Translate the invariant into these small, testable moves.
- Choose a candidate.
- Record the choice.
- Explore the next decision.
- Undo the choice before trying the next candidate.
def subsetsWithDup(nums):
res = []
nums.sort()
def backtrack(i, subset):
if i == len(nums):
res.append(subset[::])
return
subset.append(nums[i])
backtrack(i + 1, subset)
subset.pop()
while i + 1 < len(nums) and nums[i] == nums[i + 1]:
i += 1
backtrack(i + 1, subset)
backtrack(0, [])
return res