Subsets
For each element, branch on include vs exclude.
The Search Tree, Step by Step
Problem
Given an array of distinct integers, return every possible subset of its elements. The order of the subsets does not matter, and the empty subset must be included. No subset should appear more than once.
Examples
Input: nums = [1, 2, 3]
Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Input: nums = [0]
Output: [[], [0]]
The Goal
Return every subset of a list of distinct numbers, the empty one included. Their order doesn't matter, but no subset may appear twice.
Each number is either in a subset or not, so [1, 2, 3] has 2³ = 8 subsets.
Every call is an answer
Unlike a permutation, a subset doesn't have to use every number. Every path the search builds, starting from [], is a subset.
Record at every call, leaves and all.
Key Idea: Only Look Forward
Each call records its path, then tries adding each number after the last one chosen. The next call starts one past it.
Looking only forward means a set is built in one order: [1, 2] can be made, but [2, 1] can't. So no subset shows up twice.
Try only numbers after the last one chosen.
After 2, only 3 is left.
The Algorithm
def subsets(nums):
result = []
path = []
def backtrack(start):
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1)
path.pop()
backtrack(0)
return resultstart is the first number a call may add. Recursing with i + 1 keeps the search moving forward.
| Change | What happens |
|---|---|
| Loop from start, recurse with i + 1 | Each subset once |
| Loop from 0 every time | [1, 2] and [2, 1] both appear |
| Recurse with i | 1 is added again and again, forever |
Walkthrough
Run it on [1, 2, 3]. The first call records [].
Choosing 1 records [1], then the search goes deeper: [1, 2], then [1, 2, 3]. Undoing 3 and 2 leads to [1, 3].
Back at the first call, 2 starts the next branch: [2], then [2, 3]. Last comes [3]. That's 8 calls, one per subset, recorded in the order the search reaches them.
Checkpoint · predict the next step
Step 8 of 23 on the stage: Back from 3's branch: pop it, so path = [1, 2]. Try the next number.
path = [1, 2] · result = [[], [1], [1, 2], [1, 2, 3]] · start 2
Pitfalls
- Record at every call. Recording only full paths gives just
[1, 2, 3]. - Recurse with
i + 1, notstart + 1, or you get sets like[2, 2]and[3, 2]. - Append a copy,
path[:]. - Empty input gives
[[]]: one subset, the empty one. - A repeated number repeats subsets:
[1, 1]gives[1]twice. Subsets II sorts and skips a repeat at the same depth.
Which recursive call builds each subset exactly once?
Complexity
There are 2ⁿ subsets, and copying one takes up to O(n), so time is O(n · 2ⁿ). Each extra number doubles the count: four numbers make 16.
Apart from the output, space is the path and the call stack, O(n).
Every subset, once
- CallsOne per subset.O(2^n)
- Copy each subsetUp to n numbers each.O(n · 2^n)
- Path and call stackNot counting the output.O(n)
Exponential, because the answer itself has 2^n subsets.
In short
Backtrack over indices: at each step record the current partial subset, then for each remaining element, include it, recurse, and undo. Because every element is independently in or out, you enumerate all 2ⁿ subsets exactly once.
Common mistake
Producing duplicate subsets by not advancing the start index, or mutating the shared list without undoing.