/
Backtracking
Build candidate solutions step-by-step. When a step fails or finishes, undo and try the next option.
Algorithm Pattern
Combinatorial
What & Why
Backtracking is structured trial-and-error. You build a solution piece by piece (a 'choose' step), explore deeper, and when a branch is fully explored (or fails), you 'un-choose' (backtrack) and try the next option. It's the natural fit for combinatorial problems: subsets, permutations, combinations, paths.
The pattern is recursion with explicit state restoration. You modify shared state (a list, a path), recurse, then undo the modification before returning. The recursion tree visualization makes this concrete — every node is a partial solution, every leaf is a complete one.
Visualization
Code (Python)
Python
def subsets(nums):
result = []
def backtrack(start, current):
result.append(current[:])
for i in range(start, len(nums)):
current.append(nums[i]) # choose
backtrack(i + 1, current) # explore
current.pop() # un-choose (backtrack)
backtrack(0, [])
return result
Complexity
| Operation | Time | Space |
|---|---|---|
| Subsets | O(2ⁿ × n) | O(n) recursion |
| Permutations | O(n! × n) | O(n) recursion |
| Combinations | O(C(n,k) × k) | O(k) recursion |