</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

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.

What makes a backtracking branch hopeless, and how each case prunes in O(1)

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"]:

Trie-pruned word search trace emitting oath and skipping the a branch

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. 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 unsafe prune. A bound that is too aggressive cuts 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 on optimisation problems, and make sure the prune can never cut the answer.
  5. Undo everything, every time.
  6. Delete results as you find them where the structure allows, since 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.

Word Search II

Core idea: Carry a trie node alongside the grid position so a path dies the moment no dictionary word continues that way. One search of the grid finds every word, instead of re-walking it once per word.

Problem, rephrased

A word-hunt mobile game shows players a grid of letter tiles and a themed word list, and the backend must know before the round starts which listed words can actually be found on that grid. You're given an m x n board of characters, board, and a list of strings words, the round's dictionary.

Return all words from words that appear on the board. A word is built from sequentially adjacent cells (horizontal or vertical neighbours, like a finger trace sliding tile to tile), and the same cell may not be used twice within one word. Different words may reuse the same cells, and the result may be in any order.

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

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.