Core Idea

Recursion = a function calls itself with a smaller subproblem. Backtracking = recursion + undoing choices to explore all possibilities.

Google says: "Be able to solve problems recursively."

The Recursion Template

def solve(problem):
    # 1. BASE CASE — when to stop
    if problem is trivial:
        return answer

    # 2. RECURSIVE CASE — break into smaller subproblem
    smaller_problem = reduce(problem)
    return combine(solve(smaller_problem))

The Backtracking Template

def backtrack(choices, current_state, results):
    # Base case: found a valid solution
    if is_complete(current_state):
        results.append(current_state.copy())  # ⚠️ Must copy!
        return

    for choice in choices:
        if is_valid(choice, current_state):
            current_state.add(choice)          # MAKE the choice
            backtrack(choices, current_state, results)  # EXPLORE
            current_state.remove(choice)     # UNDO the choice (backtrack)

The key insight: backtracking is like exploring a tree of decisions. At each node, you try all options, and if a branch doesn’t work, you undo ("backtrack") and try the next option.

Exercises

  • Permutations — Generate all orderings

  • Subsets — Generate all subsets (power set)

  • N-Queens — Classic backtracking on a chessboard