What Problem Does It Solve?
Backtracking is for problems where you need to explore all possible configurations to find one (or all) that satisfy a set of constraints. Think of solving a maze: you walk down a corridor, hit a dead end, retrace your steps to the last junction, and try a different direction. Backtracking is that systematic retracing, applied to decision trees.
Common triggers: "Find all permutations of...", "Find all valid subsets...", "Solve this Sudoku puzzle", "Is there a valid path through...?"
The Three-Step Template
Every backtracking solution follows the same skeleton:
def backtrack(state, choices):
# Base case: is this a complete, valid solution?
if is_solution(state):
results.append(state[:]) # Record it
return
for choice in choices:
if is_valid(state, choice): # 1. CONSTRAINT CHECK
state.append(choice) # 2. MAKE CHOICE
backtrack(state, choices) # 3. RECURSE
state.pop() # 4. UNDO (backtrack)
The state.pop() line is the "undo button" — it reverses the last choice so the next iteration of the loop can try a different one.
Concrete Example: All Permutations of [1, 2, 3]
def permutations(nums):
results = []
def backtrack(current, remaining):
if not remaining:
results.append(current[:])
return
for i in range(len(remaining)):
current.append(remaining[i])
backtrack(current, remaining[:i] + remaining[i+1:])
current.pop() # Undo
backtrack([], nums)
return results
print(permutations([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Pruning: The Performance Multiplier
Backtracking without pruning is just brute-force search. The power comes from pruning — detecting invalid states early and cutting off entire branches of the decision tree before exploring them. In Sudoku, if placing a 5 in a cell immediately violates a row constraint, you skip all sub-trees that start with that 5. Good pruning can reduce the effective search space from exponential to tractable.