152. Generate All Subsets
Problem
Return all subsets of a list of distinct integers, retaining input order within each subset. Use depth-first order that emits the current subset before extending it with later indices. Empty input returns [[]]. Do not mutate nums.
Examples
Example 1
subsets([1,2])
=> [[], [1], [1, 2], [2]]A path is emitted before its extensions.
Example 2
subsets([])
=> [[]]The empty set has one subset.
Example 3
subsets([7])
=> [[], [7]]Either stop at the root or select the only value.
Reveal the worked solution and reasoning
Why this mechanism works
A subset is identified by its increasing sequence of chosen indices. The next index may be any position at or after start. Emit the current path even before it is extended: stopping now is itself a valid subset. Advancing start prevents reordered duplicates such as [2,1] after [1,2].
State and boundaries
path is a subset from strictly increasing indices. start is the first index still eligible for extension.
Protocol
- Save a copy of path.
- For each i from start onward, choose nums[i].
- Recurse with start=i+1.
- Undo that choice before trying the next i.
Visualization
[]
choose index 0 -> [1] -> [1,2]
undo to []
choose index 1 -> [2]Python implementation
def subsets(nums):
output, path = [], []
def visit(start):
output.append(path.copy())
for i in range(start, len(nums)):
path.append(nums[i])
visit(i + 1)
path.pop()
visit(0)
return output
Worked execution
subsets([1,2])
L2 subsets: output, path = [], [] nums=[1, 2]; output=[]; path=[] L4 visit: output.append(path.copy()) start=0; nums=[1, 2]; output=[[]]; path=[] L5 visit: for i in range(start, len(nums)): start=0; nums=[1, 2]; output=[[]]; path=[]; i=0 L6 visit: path.append(nums[i]) start=0; nums=[1, 2]; output=[[]]; path=[1]; i=0 L4 visit: output.append(path.copy()) start=1; nums=[1, 2]; output=[[], [1]]; path=[1] L5 visit: for i in range(start, len(nums)): start=1; nums=[1, 2]; output=[[], [1]]; path=[1]; i=1 L6 visit: path.append(nums[i]) start=1; nums=[1, 2]; output=[[], [1]]; path=[1, 2]; i=1 L4 visit: output.append(path.copy()) start=2; nums=[1, 2]; output=[[], [1], [1, 2]]; path=[1, 2] ... 6 intermediate state changes omitted ... L4 visit: output.append(path.copy()) start=2; nums=[1, 2]; output=[[], [1], [1, 2], [2]]; path=[2] L7 visit: visit(i + 1) start=0; nums=[1, 2]; output=[[], [1], [1, 2], [2]]; path=[2]; i=1 L8 visit: path.pop() start=0; nums=[1, 2]; output=[[], [1], [1, 2], [2]]; path=[]; i=1 L9 subsets: visit(0) nums=[1, 2]; output=[[], [1], [1, 2], [2]]; path=[]
Result: [[], [1], [1, 2], [2]]. A path is emitted before its extensions.
subsets([])
L2 subsets: output, path = [], [] nums=[]; output=[]; path=[] L4 visit: output.append(path.copy()) start=0; nums=[]; output=[[]]; path=[] L9 subsets: visit(0) nums=[]; output=[[]]; path=[]
Result: [[]]. The empty set has one subset.
Why the solution is correct
The empty subset is emitted at the root. Every nonempty subset has a unique increasing index sequence, followed by exactly one route through the recursion. Emitting each route's prefix covers all subsets once. Eligible indices strictly advance, so recursion terminates.
Time and space
O(n*2^n) time and output space; O(n) auxiliary path and recursion depth.
Common mistakes
Reusing i instead of i+1 permits repeated selection. Appending path without copying changes previously saved answers.
Reasoning card
State: path is a subset from strictly increasing indices. start is the first index still eligible for extension.
Invariant: path reflects decisions made before the current index.
Decision to rehearse: Use include/exclude decisions or choose-next indexing.
Finish: Undo that choice before trying the next i
Transfer exercise
Allow duplicate input values and skip equal choices only at the same recursion depth.