NeetCode #493LC-90MediumBacktrackingNC 150NC 250
← Back to All Problems#493 · #90 · Subsets II(子集 II)
📌 Problem Statement & Constraints
Given an integer array
nums that may contain duplicates, return all possible subsets (the power set) without duplicate subsets. Constraints: 1 <= nums.length <= 10, -10 <= nums[i] <= 10.💡 Core Algorithmic Approaches
- Sort the array so duplicates are adjacent, then use the loop-based subset template.
- Record the path at every node, since every partial selection is a valid subset.
- Deduplicate at each recursion level by skipping a value equal to its predecessor in the same loop.
- The level-local skip is what removes duplicate subsets while keeping legitimate repeated values in deeper levels.
💻 Benchmark Python3 Implementation
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort() # duplicates become adjacent
res = []
def dfs(start: int, path: List[int]) -> None:
res.append(path[:]) # every node is a valid subset
for j in range(start, len(nums)):
# skip duplicates at THIS level only
if j > start and nums[j] == nums[j - 1]:
continue
path.append(nums[j])
dfs(j + 1, path)
path.pop()
dfs(0, [])
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * 2^n): there are at most 2^n subsets, each copied in O(n).
💾 Space Complexity
O(n) for the recursion path plus the output.
⚠️ Interview Pitfalls & Follow-ups
- Using
j > 0in the duplicate skip: values legitimately repeated at deeper levels would be wrongly skipped, losing valid subsets. - Not sorting: duplicates would not be adjacent and the skip would not work.
- Recording only at the leaves: that would produce only the full set.
- Using a set of tuples for deduplication: O(n) extra work per subset; the level-local skip is free.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.