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, so 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.
Core idea: build the structure that answers "is this branch still worth exploring?" in O(1) (a trie, a palindrome table, a pruning rule) 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. That ordering detail is what makes the table work.
3. Prune what cannot matter
For optimisation problems, cut any branch that cannot change the answer. In Path with Maximum Gold the search never steps onto a cell with no gold. In Optimal Account Balancing the recursion skips anyone whose balance is already zero, only pairs a balance with one of the opposite sign, and tries each distinct balance value once per level, since equal values lead to identical subtrees.
A prune must never rule out a branch that could actually win. If you add a bound on the best count so far, make it optimistic (assume everything remaining goes perfectly): that is always safe, a pessimistic one is not.
The account-balancing lesson also shows a second route: a bitmask DP over subsets that finds the maximum number of zero-sum groups, and the answer is the number of non-zero balances minus that count.
4. A 30-second worked example (trie pruning)
Grid with o a a / e t a / i h k, dictionary ["oath", "pea", "eat", "rain"]:
On this grid only oath is on the board (o, a, t, h along a connected path). The other starts are the point: without a trie you would explore every path from those cells, and with one a single lookup rules out the whole subtree.
5. Where you'll actually meet this
- Autocomplete and spell-checking. Tries let a search discard every candidate that is not a prefix of a known word.
- Financial settlement. Optimal Account Balancing is the problem of minimising transfers when settling group debts, as in expense-splitting tools.
- Resource pathfinding. Maximum-value route collection under movement constraints, as in game maps or route planning.
- 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ⁿ) time, bound by the size of the output, with O(1) palindrome checks after an O(n²) table.
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(M · 4 · 3^(L-1)) worst case for M cells and longest word L, far better in practice because the trie cuts most paths.
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, skipping repeated balance values. A bitmask DP over subsets is the alternative.
Pattern: netting + backtracking. Target: O((N-1)!) worst case for backtracking, O(N · 2^N) for the bitmask DP, where N is the number of non-zero balances (at most 12).
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(K · 3^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.
imust 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 unsafe prune. A bound that is too aggressive cuts the actual answer; when in doubt, be optimistic.
8. Key takeaways
- Preparation is the algorithm. Build the structure that answers "is this branch alive?" in O(1).
- Carry the structure with the search. A trie node beside a grid position is the canonical example.
- Precompute repeated queries rather than recomputing them inside the recursion.
- Prune on optimisation problems, and make sure the prune can never cut the answer.
- Undo everything, every time.
- Delete results as you find them where the structure allows, since it prunes the remaining search.
- 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.
Palindrome Partitioning
Core idea: Backtrack over cut points, and precompute an
is_palindrome[i][j]table inO(n^2)so that each "is this piece a palindrome?" test inside the recursion isO(1). The table is filled by increasing substring length, so the inner substrings[i+1..j-1]is always known before it is needed.
Problem, rephrased
A word-puzzle app builds "mirror levels" from ordinary words: a word is sliced into pieces, and a slicing is playable only if every piece reads the same forwards and backwards. You're given a string s, the word for the next level.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson