NeetCode #488LC-78MediumBacktrackingNC 150NC 250
← Back to All Problems#488 · #78 · Subsets(子集)
📌 Problem Statement & Constraints
Given an integer array
nums of unique elements, return all possible subsets (the power set) in any order. Constraints: 1 <= nums.length <= 10, -10 <= nums[i] <= 10.💡 Core Algorithmic Approaches
- Every element is either included or excluded, so there are exactly
2^nsubsets. - A DFS over the index decides each element in turn, recording the path at every node (not just at the leaves).
- Recording at every node is what produces the partial subsets as well as the full ones.
- An iterative bitmask alternative enumerates
0 .. 2^n - 1and includes elementiwhen bitiis set.
💻 Benchmark Python3 Implementation
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
def dfs(i: int, path: List[int]) -> None:
if i == len(nums):
res.append(path[:]) # copy, not a reference
return
dfs(i + 1, path) # exclude nums[i]
path.append(nums[i])
dfs(i + 1, path) # include nums[i]
path.pop() # backtrack
dfs(0, [])
return res
# Bitmask enumeration: exactly 2^n subsets
class Solution2:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res = []
for mask in range(1 << n):
res.append([nums[i] for i in range(n) if mask >> i & 1])
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * 2^n): there are 2^n subsets, each requiring O(n) to copy.
💾 Space Complexity
O(n) for the recursion path plus O(n * 2^n) for the output.
⚠️ Interview Pitfalls & Follow-ups
- Appending
pathwithout copying: every entry would reference the same list, which is mutated afterwards. - Recording only at the leaves: that would produce only the full set, not all subsets.
- Forgetting
path.pop(): the backtracking state would leak between branches. - Assuming duplicates may exist: the problem guarantees unique elements, which is why no deduplication is needed (contrast with 90).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.