Recursion & Backtracking: Complete Guide

Recursion & Backtracking

Backtracking is systematic exploration of all possible solutions, with pruning to skip dead ends.

Core Framework

backtrack(state, choices):
    if is_solution(state):
        record(state)
        return
    for choice in choices:
        if is_valid(state, choice):
            make_choice(state, choice)
            backtrack(state, next_choices)
            undo_choice(state, choice)  # BACKTRACK

7 Core Patterns

1. Subsets / Power Set — include or exclude each element 2. Permutations — arrange all elements 3. Combinations — choose k from n (order doesn't matter) 4. Constraint satisfaction — N-Queens, Sudoku 5. Path finding — maze, word search 6. Partition — split into groups with constraints 7. Expression generation — add operators, generate parentheses

Pruning Strategies

• Early termination: Check constraints before recursing deeper
• Ordering: Sort first to enable branch-and-bound
• Bounding: Skip when remaining can't improve best
• Symmetry breaking: Avoid generating equivalent states

Time Complexity

When to Use

• "Generate all..." — backtracking
• "Find all valid..." — backtracking with constraint check
• "Count/enumerate..." — backtracking or DP
• "Find if possible..." — often DP is better, but backtracking works