Backtracking

Backtracking is a powerful technique for exploring all possible solutions to a problem. Learn to systematically search solution spaces, prune invalid paths, and find optimal solutions through controlled recursion.

Core Concept:
Build solution incrementally, abandoning (backtracking) when constraints are violated. Think of it as “try, if doesn’t work, undo and try another way.”

Common Applications:

Combinatorial: Permutations, combinations, subsets
Constraint satisfaction: N-Queens, Sudoku solver
Path finding: Word search, maze solving
Partitioning: Palindrome partitioning, subset sum

Template Pattern:

def backtrack(state, choices):
if is_solution(state):
add_to_results(state)
return

for choice in choices:
make_choice(choice)
backtrack(new_state, remaining_choices)
undo_choice(choice) # Backtrack!

Optimization: Prune branches early, use memoization when subproblems overlap.