Backtracking

Backtracking explores a search tree by making a choice, recursing, then undoing the choice. The invariant is that the current path is always valid.

Pattern A: Cartesian product expansion

Use when: each position has a small set of choices.

Invariant: path length equals the number of fixed positions built so far.

Skeleton:

func dfs(i, path):
    if i == n: record; return
    for option in choices[i]:
        path.push(option)
        dfs(i+1, path)
        path.pop()

Problems:

• letter-combinations-of-a-phone-number.

Pattern B: Combinations (choose / skip)

Use when: you need combinations in increasing order.

Invariant: start ensures no duplicates and increasing order.

Skeleton:

func dfs(start, path):
    if len(path) == k: record; return
    for i in start..n:
        path.push(i)
        dfs(i+1, path)
        path.pop()

Problems:

• combinations.

Pattern C: Permutations

Use when: you need all orderings of distinct items.

Invariant: used[i] indicates whether nums[i] is in the current path.

Skeleton:

func dfs(path):
    if len(path) == n: record; return
    for i in 0..n-1:
        if used[i]: continue
        used[i] = true
        path.push(nums[i])
        dfs(path)
        path.pop()
        used[i] = false

Problems:

• permutations.

Pattern D: Combination sum (reuse allowed)

Use when: you can reuse elements and order does not matter.

Invariant: we only recurse on i or later to avoid duplicates.

Skeleton:

func dfs(start, remain, path):
    if remain == 0: record; return
    for i in start..n-1:
        if candidates[i] > remain: continue
        path.push(candidates[i])
        dfs(i, remain - candidates[i], path)
        path.pop()

Problems:

• combination-sum.

Pattern E: Balanced parentheses

Use when: you must build strings with constrained counts.

Invariant: openUsed >= closeUsed and openUsed <= n.

Skeleton:

func dfs(openUsed, closeUsed, path):
    if len(path) == 2*n: record; return
    if openUsed < n: add '(' and recurse
    if closeUsed < openUsed: add ')' and recurse

Problems:

• generate-parentheses.

Pattern F: N-Queens with constraints

Use when: you must place items with no conflicts.

Invariant: columns and diagonals sets track used lines.

Skeleton:

func dfs(row):
    if row == n: count++; return
    for col in 0..n-1:
        if col or diag1 or diag2 used: continue
        mark col/diag
        dfs(row+1)
        unmark col/diag

Problems:

• n-queens-ii.

Pattern G: Grid word search

Use when: you need to find a path spelling a word.

Invariant: visited cells are not reused in the current path.

Skeleton:

func dfs(r,c,i):
    if i == len(word): return true
    if out of bounds or visited or board[r][c] != word[i]: return false
    mark visited
    if dfs(neighbors, i+1): return true
    unmark visited
    return false

Problems:

• word-search.

When to use Backtracking (checklist)

• You need to enumerate or count combinatorial possibilities.
• Constraints allow pruning to keep the search manageable.

Common failures (checklist)

• Forgetting to undo state changes when returning.
• Allowing duplicates by not controlling the start index.
• Missing pruning when partial sums exceed targets.

Problem mapping

• letter-combinations-of-a-phone-number: Cartesian product over digits.
• combinations: choose/skip with start index.
• permutations: used array.
• combination-sum: reuse allowed, non-decreasing start.
• generate-parentheses: open/close count constraints.
• n-queens-ii: column/diagonal constraints.
• word-search: DFS with visited grid.