Backtracking Problems

What is this?

Every problem here has a brute force you could write in two minutes and never run to completion. What makes them tractable is preparation: build a structure before the search that lets you abandon a branch after one comparison rather than after exploring it.

Searching a grid for 3,000 dictionary words by trying each word separately is hopeless. Walking a trie alongside the grid, so a path dies the instant it stops spelling a prefix of any word, finishes comfortably.

💡 Fun fact: Word Search II is the problem that makes tries click. Running Word Search I once per dictionary word re-walks the same grid paths thousands of times. Inserting every word into a trie and carrying a trie node alongside the grid position means a path is abandoned the moment no word continues that way — one search finds them all. The standard refinement is to delete words from the trie as they are found, which prunes the tree further as the search proceeds.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: build the structure that answers "is this branch still worth exploring?" in O(1) — a trie, a palindrome table, a running bound — and the exponential search becomes something that finishes.

1. Carry a structure alongside the search

def dfs(r, c, node, path):
    ch = board[r][c]
    if ch not in node.children:
        return                          # dead: no word continues this way
    nxt = node.children[ch]
    if nxt.word:
        found.add(nxt.word)
        nxt.word = None                 # emit once, and prune the branch
    board[r][c] = '#'                   # mark visited
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if in_bounds(nr, nc) and board[nr][nc] != '#':
            dfs(nr, nc, nxt, path + ch)
    board[r][c] = ch                    # UNDO

The state carried is the pair (grid position, trie node). Both advance together, and the first line is the entire pruning: if the current letter is not a child of the current trie node, no word in the dictionary can be completed along this path, so stop immediately.

2. Precompute what the search asks repeatedly

Palindrome Partitioning asks "is s[i..j] a palindrome?" at every step. Answering it from scratch is O(n) each time. Precomputing a table in O(n²) makes each query O(1):

is_pal = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
    for j in range(i, n):
        if s[i] == s[j] and (j - i < 2 or is_pal[i+1][j-1]):
            is_pal[i][j] = True

The loop runs i downward so that is_pal[i+1][j-1] is already computed when it is needed — the small ordering detail that makes the table work.

3. Prune by bound

For optimisation problems, cut any branch that cannot beat what you already have. In Path with Maximum Gold the search abandons a cell with no gold immediately; in Optimal Account Balancing the recursion skips anyone whose balance is already zero and stops once the transaction count reaches the best found so far.

The bound must be admissible — it may never rule out a branch that could actually win. An optimistic estimate (assume everything remaining goes perfectly) is always safe; a pessimistic one is not.

4. A 30-second worked example (trie pruning)

Grid with o a a / e t a / i h k, dictionary ["oath", "pea", "eat", "rain"]:

start at (0,0) 'o'  → trie has 'o' (oath) ✓ continue
  (0,1) 'a'         → 'o'→'a' exists ✓
    (1,1) 't'       → 'o'→'a'→'t' exists ✓
      (1,0) 'e'     → 'o'→'a'→'t'→'e'? no ✗  dead, back up
      (2,1) 'h'     → 'o'→'a'→'t'→'h' ✓ and marks a word → emit "oath"

start at (0,1) 'a'  → trie root has no 'a' child ✗  ENTIRE branch skipped
start at (1,0) 'e'  → 'e' exists (eat) ✓ continue …

The second start is the point. Without a trie you would explore every path from that cell; with one, a single dictionary lookup rules out the whole subtree.

5. Where you'll actually meet this

• Autocomplete and spell-checking. Trie-guided search over a grid or an edit-distance space is how suggestion engines prune.
• Financial settlement. Optimal Account Balancing is the real problem of minimising transfers when settling group debts, used by expense-splitting apps.
• Resource pathfinding. Maximum-value route collection under movement constraints — mining, delivery routing, game AI.
• Text segmentation. Splitting a string into valid pieces (words, tokens, palindromes) with a precomputed validity table.
• Query optimisation. Branch-and-bound over join orders, cutting plans that already exceed the best known cost.

6. Problems in this chapter

▶ Palindrome Partitioning

All ways to split a string into palindromic substrings. Precompute the palindrome table, then backtrack over split points.
Pattern: precomputed validity + backtracking. Target: O(n · 2ⁿ) output-bound, with O(1) palindrome checks.

▶ Word Search II

Find every dictionary word present in a grid. One search carrying a trie node alongside the grid position, deleting words as they are found.
Pattern: trie-pruned DFS. Target: O(mn · 4^L) worst case, far better in practice.

▶ Optimal Account Balancing

Minimum transactions to settle a group's debts. Net every person's balance, discard the zeros, then backtrack over who settles with whom, bounded by the best count found.
Pattern: netting + bounded backtracking. Target: exponential in the number of non-zero balances, which is small.

▶ Path with Maximum Gold

Collect the most gold on a path that never revisits a cell. DFS from every gold cell with visited-marking and undo.
Pattern: exhaustive DFS with backtracking. Target: O(mn · 4^k) where k is the number of gold cells.

7. Common pitfalls 🚫

• Forgetting to undo. Restoring the board cell, the visited flag or the balance is what makes sibling branches correct.
• Running the single-word search per word. That is the whole reason Word Search II exists — one trie-guided pass replaces thousands.
• Not removing found words from the trie. Duplicates get emitted and the search keeps exploring branches with nothing left to find.
• Recomputing palindrome checks. O(n) per check inside an exponential search is what makes the naive version time out.
• Building the palindrome table in the wrong direction. i must decrease so the inner substring is already known.
• Settling zero balances. Anyone already at zero must be skipped, or the search wanders through pointless states.
• An inadmissible bound. A bound that is too aggressive prunes the actual answer; when in doubt, be optimistic.

8. Key takeaways

1. Preparation is the algorithm. Build the structure that answers "is this branch alive?" in O(1).
2. Carry the structure with the search. A trie node beside a grid position is the canonical example.
3. Precompute repeated queries rather than recomputing them inside the recursion.
4. Prune by bound on optimisation problems, and make sure the bound is admissible.
5. Undo everything, every time.
6. Delete results as you find them where the structure allows — it prunes the remaining search.
7. Why interviewers like it: the naive solution is always available and always too slow, so the entire signal is in what you can justify skipping.

Order: Palindrome Partitioning → Word Search II → Optimal Account Balancing → Path with Maximum Gold.