Permutations
StopSearch tree
- CH1 path
53/53
Try every unused number at each place, and free it again on the way back.
Step through it →Backtracking
Backtracking builds an answer one choice at a time and undoes each choice to try the next, so it walks every branch of a tree of choices.
Subsets: every call records one
StopSearch tree
nums
- CH1 path
backtrack(0) starts with an empty path. Record [], the empty subset.
Typical cost Exponential in the worst case; pruning is what makes it tractableFull lesson: Subsets →
When to reach for it
- You're asked for all of something: subsets, orderings, combinations, placements.
- An answer is a sequence of choices, each from a small set.
- Some partial answers can already be ruled out, so whole branches can be cut.
- The output itself is exponential, so nothing much faster exists.
What stays true
Each choice is appended just before its call and popped just after the call returns. So when a call runs, the path holds its own choices and nothing left over from a sibling.
The path is the way down
StopSearch tree
InvariantThe path holds exactly the choices from the first call down to the running one.✓ Holds
- CH1 path
Start with an empty path: every number is free.
Break it
Each input here has tripped up a version of this code. The stage runs the one that gets it right.
Recursing with i + 1 instead of i would allow 2 only once and miss [2, 2, 2, 2].
Backtracking on the inputs that trip it up
StopSearch tree
- CH1 path
Sort the candidates: [2]. Start with remaining = 8 and an empty path.
Answer[[2, 2, 2, 2]]Steps15
Variants
Combination sum
StopSearch tree
- CH1 path
38/38
Recurse from the same index to reuse a candidate, and stop once one is too big.
Step through it →The code
The same algorithm in plain Python. The lit line is the one the current frame came from.
Subsets: every call records one
StopSearch tree
- CH1 path
backtrack(0) starts with an empty path. Record [], the empty subset.
subsets.py
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 result