Back to Topics
Backtracking
Backtracking is a systematic trial-and-error search that builds candidates incrementally and abandons (backtracks) a path as soon as it determines the path cannot lead to a valid solution. It explores a decision tree via DFS, pruning branches early to avoid unnecessary work.
Key Ideas
- Template: choose → explore → unchoose (undo the choice after recursion returns)
- State is mutated and then restored — classic with append/pop on a path list
- Pruning is essential: check constraints before recursing, not after
- Subset problems: include or exclude each element → 2ⁿ leaves
- Permutation problems: swap elements in-place → n! leaves
- Combination problems: advance start index to avoid duplicates
Complexity
| Operation | Time | Space |
|---|---|---|
| Subsets | O(2ⁿ) | O(n) |
| Permutations | O(n!) | O(n) |
| Combinations | O(C(n,k)) | O(k) |
| N-Queens | O(n!) | O(n) |
Common Patterns
Choose / Explore / UnchooseCore template: mutate state, recurse, then restore state on return.
Subset / Power SetAt each index: include the element or skip it. Two recursive calls.
Permutations via SwapSwap element at i with each subsequent element; recurse; swap back.
Constraint PruningAdd guards before recursing — e.g. skip if current sum already exceeds target.
Code Example
Generate all subsetspython
def subsets(nums: list[int]) -> list[list[int]]:
result: list[list[int]] = []
path: list[int] = []
def backtrack(start: int) -> None:
result.append(list(path)) # snapshot current subset
for i in range(start, len(nums)):
path.append(nums[i]) # choose
backtrack(i + 1) # explore
path.pop() # unchoose
backtrack(0)
return result💡
Draw the decision tree first. Each level is a choice; each leaf is a complete candidate. Pruning removes entire subtrees.