Recursion & backtracking

Enumerate a combinatorial universe by hand. Recursion walks a recursively-defined space; backtracking is recursion plus undo. Once you internalise choose → explore → un-choose, every subset / permutation / board problem is the same three lines.

Why this paradigm

A huge class of interview problems asks you to enumerate or search a space of arrangements: every subset, every permutation, every way to place 8 queens, every way to cut a string into palindromes. These spaces are exponential, so there is no clever closed form — you must walk the space. Recursion is the natural tool because the space itself is recursively defined: "a permutation of n items = pick a first item, then a permutation of the remaining n−1."

Backtracking is recursion plus undo. You build a partial solution one choice at a time; when a choice leads nowhere (or you finish a solution) you undo the choice and try the next one, reusing the same mutable buffer. That undo is the only thing separating backtracking from plain recursion.

Recursion from first principles

Every recursive function is two things and nothing more:

1. Base case — an input small enough to answer directly, no recursion.
2. Recursive case — reduce the problem to a strictly smaller instance of itself, call yourself, and combine.

If the recursive case does not make the input strictly smaller (closer to the base case), you get infinite recursion → stack overflow. That is the #1 bug.

Recursion-tree thinking

Draw the calls as a tree: the root is the original call, each node's children are the calls it makes. This tree is your model for both correctness and cost:

• The leaves are base cases (the answers / solutions).
• Time ≈ (number of nodes) × (work per node).
• Space ≈ (height of the tree) for the call stack (+ output size).

To count nodes: a tree that branches b ways and is h deep has up to b^h leaves and ~b^(h+1) total nodes — i.e. exponential. That is why these problems are exponential, and why pruning (cutting branches early) is the whole game.

The backtracking template (memorize this)

def backtrack(state, path, results):
    if is_complete(state):          # reached a leaf / valid solution
        results.append(path.copy()) # COPY — path keeps mutating!
        return
    for choice in candidates(state):
        if not valid(choice):       # PRUNE: skip dead branches early
            continue
        path.append(choice)         # CHOOSE
        backtrack(advance(state), path, results)   # EXPLORE
        path.pop()                  # UN-CHOOSE  (the "back" in backtrack)

The three beats — choose → explore → un-choose — are the spine of every problem below. The only things that change per problem are: what a "choice" is, how you advance, when a path is complete, and what counts as a valid (un-pruned) choice.

Warmup — recursion fundamentals

Two anchors. factorial is a single chain (branching factor 1, depth n). fib branches two ways and recomputes the same subproblem many times — the textbook overlapping-subproblems smell that motivates DP.

def factorial(n: int) -> int:
    if n <= 1:               # BASE CASE: smallest input we answer directly.
        return 1
    return n * factorial(n - 1)   # RECURSIVE CASE: strictly smaller (n-1).


def fib(n: int) -> int:
    if n < 2:                # BASE CASE.
        return n
    return fib(n - 1) + fib(n - 2)   # TWO recursive calls -> branching tree.

Subsets — LeetCode 78

Generate the power set (all 2^n subsets). Mental model: walk the array left to right; at each index make a binary choice — include nums[i] or not. The recursion tree has depth n and branching factor 2 → exactly 2^n leaves, one per subset. Because every node along the way is itself a valid subset, we record path at every node (not just leaves) using the start-index sweep. Using a start index (rather than a visited set) guarantees we only ever move forward, so we never produce the same subset in two orders.

def subsets(nums: List[int]) -> List[List[int]]:
    res: List[List[int]] = []

    def backtrack(start: int, path: List[int]) -> None:
        res.append(path.copy())          # every node is a valid subset -> record
        for i in range(start, len(nums)):
            path.append(nums[i])         # CHOOSE nums[i]
            backtrack(i + 1, path)       # EXPLORE: only indices AFTER i
            path.pop()                   # UN-CHOOSE

    backtrack(0, [])
    return res

Permutations — LeetCode 46

All n! orderings of distinct numbers. A permutation = pick any unused element for the next slot, recurse on the rest. Order matters here (unlike subsets), so a choice may reuse an earlier index — we track which elements are used. The tree has n choices at the root, n−1 at depth 1, ... → n! leaves.

def permutations(nums: List[int]) -> List[List[int]]:
    res: List[List[int]] = []
    used = [False] * len(nums)

    def backtrack(path: List[int]) -> None:
        if len(path) == len(nums):       # BASE CASE: a full ordering -> a leaf
            res.append(path.copy())
            return
        for i in range(len(nums)):
            if used[i]:                  # PRUNE: each element used at most once
                continue
            used[i] = True               # CHOOSE
            path.append(nums[i])
            backtrack(path)              # EXPLORE
            path.pop()                   # UN-CHOOSE (and free the element)
            used[i] = False

    backtrack([])
    return res

Combinations — LeetCode 77

All k-element subsets of {1..n} (order does not matter). Like subsets, but with a fixed target size k; the start index keeps selections increasing so we never repeat a combination. Pruning: if not enough numbers remain to reach size k, abandon the branch. We need (k - len(path)) more; available from i..n is (n - i + 1). Stop the loop once that is impossible — this cuts a large fraction of the tree.

def combinations(n: int, k: int) -> List[List[int]]:
    res: List[List[int]] = []

    def backtrack(start: int, path: List[int]) -> None:
        if len(path) == k:               # BASE CASE: full combination
            res.append(path.copy())
            return
        need = k - len(path)
        # PRUNE: last start that still leaves `need` numbers is n - need + 1.
        for i in range(start, n - need + 2):
            path.append(i)               # CHOOSE
            backtrack(i + 1, path)       # EXPLORE forward only
            path.pop()                   # UN-CHOOSE

    backtrack(1, [])
    return res

Combination sum — LeetCode 39

All multisets of candidates summing to target. Each number may be reused unlimited times. Key twist vs combinations: because reuse is allowed, the recursive call uses i (not i+1) so the same number can be chosen again. We still pass a start index to avoid permuted duplicates ([2,3] and [3,2] are the same multiset). Pruning: sort candidates; once a candidate exceeds the remaining target, every later (larger) candidate also does → break the loop entirely.

def combination_sum(candidates: List[int], target: int) -> List[List[int]]:
    res: List[List[int]] = []
    candidates = sorted(candidates)

    def backtrack(start: int, remaining: int, path: List[int]) -> None:
        if remaining == 0:               # BASE CASE: exact hit -> record
            res.append(path.copy())
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:    # PRUNE: sorted -> rest are bigger
                break
            path.append(candidates[i])       # CHOOSE
            backtrack(i, remaining - candidates[i], path)  # reuse -> pass i
            path.pop()                       # UN-CHOOSE

    backtrack(0, target, [])
    return res

Generate parentheses — LeetCode 22

All valid strings of n pairs of parentheses. The choice at each step: add '(' or ')'. The cleverness is pruning via two counters so we only ever build valid prefixes: may add '(' while open < n; may add ')' only while close < open (else we'd close an unopened pair). Counts of valid strings are the Catalan numbers C(n) ~ 4^n / n^1.5.

def generate_parentheses(n: int) -> List[str]:
    res: List[str] = []

    def backtrack(path: List[str], open_count: int, close_count: int) -> None:
        if len(path) == 2 * n:           # BASE CASE: complete string
            res.append("".join(path))
            return
        if open_count < n:               # valid to open another pair
            path.append("(")
            backtrack(path, open_count + 1, close_count)
            path.pop()
        if close_count < open_count:     # PRUNE: only close what is open
            path.append(")")
            backtrack(path, open_count, close_count + 1)
            path.pop()

    backtrack([], 0, 0)
    return res

Word search — LeetCode 79 (grid DFS + visited)

Does word exist as a path of orthogonally-adjacent cells, with no cell reused? This is backtracking on a grid. The "choice" is which of the 4 neighbours to step into next. The crucial backtracking move: mark a cell visited before recursing, then unmark it on the way out so other search paths may use it. We mutate the board in place (cheap sentinel) instead of a separate set. Pruning: bail the instant the current cell mismatches the expected letter.

def word_search(board: List[List[str]], word: str) -> bool:
    if not word:
        return True
    rows, cols = len(board), len(board[0])

    def dfs(r: int, c: int, idx: int) -> bool:
        if idx == len(word):             # BASE CASE: matched every letter
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False                 # PRUNE: off the board
        if board[r][c] != word[idx]:
            return False                 # PRUNE: wrong letter here
        tmp = board[r][c]
        board[r][c] = "#"                # CHOOSE: mark visited (in-place)
        found = (dfs(r + 1, c, idx + 1) or dfs(r - 1, c, idx + 1) or
                 dfs(r, c + 1, idx + 1) or dfs(r, c - 1, idx + 1))   # EXPLORE
        board[r][c] = tmp                # UN-CHOOSE: restore the cell
        return found

    for i in range(rows):
        for j in range(cols):
            if dfs(i, j, 0):             # try every starting cell
                return True
    return False

N-Queens — LeetCode 51

Place n queens on an n×n board so none attack each other. Mental model: place one queen per row (so rows never conflict by construction). For each row choose a column; a placement is valid if its column and its two diagonals are unused. We track three sets:

O(1) conflict checks via these sets are the key efficiency trick — far better than re-scanning the board each time. Notice that every add on the way down is mirrored by a discard on the way back up.

def solve_n_queens(n: int) -> List[List[str]]:
    res: List[List[str]] = []
    cols = set()
    diag = set()        # r - c
    anti = set()        # r + c
    placement: List[int] = []   # placement[r] = column of the queen in row r

    def backtrack(r: int) -> None:
        if r == n:                       # BASE CASE: all rows filled -> a board
            board = []
            for col in placement:
                board.append("." * col + "Q" + "." * (n - col - 1))
            res.append(board)
            return
        for c in range(n):
            if c in cols or (r - c) in diag or (r + c) in anti:
                continue                 # PRUNE: this cell is attacked
            cols.add(c); diag.add(r - c); anti.add(r + c)   # CHOOSE
            placement.append(c)
            backtrack(r + 1)             # EXPLORE next row
            placement.pop()              # UN-CHOOSE (mirror every add)
            cols.discard(c); diag.discard(r - c); anti.discard(r + c)

    backtrack(0)
    return res


def total_n_queens(n: int) -> int:
    """Count-only variant (LeetCode 52) — same tree, just count the leaves."""
    return len(solve_n_queens(n))

Palindrome partitioning — LeetCode 131

Every way to cut s so each piece is a palindrome. The choice at each step: where to make the next cut. From position start, try every prefix s[start:end]; if it is a palindrome, fix it as the next piece and recurse on the remainder. The cut positions form the tree. Pruning: skip any prefix that is not a palindrome — no point exploring a partition whose first piece is already invalid.

def partition_palindromes(s: str) -> List[List[str]]:
    res: List[List[str]] = []

    def is_pal(sub: str) -> bool:
        return sub == sub[::-1]

    def backtrack(start: int, path: List[str]) -> None:
        if start == len(s):              # BASE CASE: consumed the whole string
            res.append(path.copy())
            return
        for end in range(start + 1, len(s) + 1):
            piece = s[start:end]
            if not is_pal(piece):        # PRUNE: only palindromic first pieces
                continue
            path.append(piece)           # CHOOSE this cut
            backtrack(end, path)         # EXPLORE the remainder
            path.pop()                   # UN-CHOOSE

    backtrack(0, [])
    return res

Each function is self-verifying; for example partition_palindromes("aab") yields [["a","a","b"], ["aa","b"]] and subsets([1,2,3]) returns exactly 2^3 = 8 distinct subsets.