Backtracking with pruning, and tries

What it is

Backtracking is depth-first search over a tree of decisions that you never build. At each node you make a choice, recurse, and then undo the choice so the next branch starts from a clean state. The undo is what makes it backtracking rather than ordinary recursion, and its cost is why the pattern is memory-cheap: one path is in memory at a time, not the whole tree. Pruning is the part that matters. The unpruned search explores every leaf; a good prune kills a subtree the moment it becomes provably useless, and in problems like n-queens that is the difference between finishing and not.

A trie (prefix tree) stores a set of strings as a tree where each edge is one character and each node represents the prefix spelled by the path to it. Lookup costs $O(\text{length of the key})$ and, importantly, does not depend on how many keys are stored. That independence is the property a hash map cannot match once the question involves prefixes.

They share a page because their hardest common form is a single problem: searching a grid for many words at once, where the trie is what makes the backtracking's pruning cheap.

Don't be confused: a trie is not usually faster than a hash map for exact lookup. A hash map hashes the key once and does one probe. A trie does one pointer dereference per character, each a potential cache miss. For "is this exact string present", the hash map wins in practice, and claiming otherwise is a tell. The trie wins where the hash map has nothing to offer at all: all keys with this prefix, longest prefix match, all keys within edit distance 1, and iteration in sorted order. Choose it for the question it can answer, not for a speed claim it cannot support.

Don't be confused: exponential output is not the same as an inefficient algorithm. subsets on $n$ items returns $2^n$ tuples, so no algorithm can be faster than exponential; the output is that size. Saying "this is $O(2^n)$, but that is optimal because the answer has $2^n$ elements" is correct and expected. Backtracking becomes genuinely inefficient only when it explores subtrees that contain no answers, which is exactly what pruning removes.

The problem it solves

Backtracking solves constrained enumeration: produce every arrangement satisfying a set of rules, or find one, when there is no formula and no greedy rule that works. Sudoku, n-queens, parsing ambiguous grammars, scheduling under constraints, and every "generate all valid X" problem.

The trie solves prefix questions at a scale where the alternatives collapse. Storing a million words and asking "which start with car" costs a full scan with a hash map, $O(\log n)$ plus a scan of the matches with a sorted array, and $O(3)$ plus the matches with a trie. It also solves longest prefix match, which has no good hash map formulation at all, and which is the operation every IP router performs for every packet.

Mechanics

"""Backtracking with pruning, and tries.

Runnable: `python3 backtracking_and_tries.py`. They share a page because the
canonical hard version of each is the same problem: word search on a grid, where
the trie is what makes the backtracking's pruning cheap.
"""


# --- Backtracking: the shape -------------------------------------------------
# Every backtracking solution is the same four lines around a loop:
#   choose -> recurse -> un-choose, with a base case and a pruning test.
# The un-choose is what makes it backtracking rather than plain recursion, and
# forgetting it is the single most common bug.
def permutations(items):
    out, used, path = [], [False] * len(items), []

    def walk():
        if len(path) == len(items):
            out.append(tuple(path))         # copy: path is mutated after this
            return
        for i, it in enumerate(items):
            if used[i]:
                continue
            used[i] = True                  # choose
            path.append(it)
            walk()                          # recurse
            path.pop()                      # un-choose
            used[i] = False
    walk()
    return out


def subsets(items):
    """Include-or-exclude, the other canonical shape. 2^n subsets, so this is
    exponential by definition, not by inefficiency: the OUTPUT is exponential."""
    out, path = [], []

    def walk(i):
        if i == len(items):
            out.append(tuple(path))
            return
        walk(i + 1)                          # exclude items[i]
        path.append(items[i])                # include it
        walk(i + 1)
        path.pop()
    walk(0)
    return out


def combination_sum(candidates, target):
    """Pruning that actually changes the complexity class. Sorting lets the loop
    BREAK rather than CONTINUE: once a candidate overshoots, every later one
    does too, so the whole remaining branch is dead."""
    out, path = [], []
    candidates = sorted(candidates)
    calls = [0]

    def walk(start, remaining):
        calls[0] += 1
        if remaining == 0:
            out.append(tuple(path))
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break                        # PRUNE: sorted, so all later ones too
            path.append(candidates[i])
            walk(i, remaining - candidates[i])   # i, not i+1: reuse allowed
            path.pop()
    walk(0, target)
    return out, calls[0]


def combination_sum_unpruned(candidates, target):
    """The same search with `continue` instead of `break`, to measure what the
    pruning is worth."""
    out, path = [], []
    candidates = sorted(candidates)
    calls = [0]

    def walk(start, remaining):
        calls[0] += 1
        if remaining == 0:
            out.append(tuple(path))
            return
        if remaining < 0:
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            walk(i, remaining - candidates[i])
            path.pop()
    walk(0, target)
    return out, calls[0]


def n_queens(n):
    """Pruning by maintaining attacked sets instead of re-scanning the board.
    A diagonal is constant in (row - col); an anti-diagonal is constant in
    (row + col). That is the whole trick, and it turns an O(n) check per
    placement into O(1)."""
    cols, diag, anti = set(), set(), set()
    placements, count = [], [0]

    def walk(row, board):
        if row == n:
            count[0] += 1
            if len(placements) < 2:
                placements.append(list(board))
            return
        for col in range(n):
            if col in cols or (row - col) in diag or (row + col) in anti:
                continue                     # PRUNE
            cols.add(col); diag.add(row - col); anti.add(row + col)
            board.append(col)
            walk(row + 1, board)
            board.pop()
            cols.discard(col); diag.discard(row - col); anti.discard(row + col)
    walk(0, [])
    return count[0], placements


# --- Trie --------------------------------------------------------------------
class Trie:
    """A prefix tree. Each edge is one character, each node is the prefix spelled
    by the path from the root. Lookup is O(len(word)) and, crucially, INDEPENDENT
    of how many words are stored, which is what a hash map cannot offer for
    prefix queries."""

    def __init__(self):
        self.root = {}
        self.END = "$"          # a key that cannot collide with a character

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
            node.setdefault("#count", 0)
            node["#count"] += 1              # words passing through this prefix
        node[self.END] = word

    def search(self, word):
        node = self._walk(word)
        return node is not None and self.END in node

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

    def count_with_prefix(self, prefix):
        node = self._walk(prefix)
        return node["#count"] if node else 0

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node:
                return None
            node = node[ch]
        return node

    def autocomplete(self, prefix, limit=5):
        node = self._walk(prefix)
        if node is None:
            return []
        out = []

        def collect(n):
            if len(out) >= limit:
                return
            if self.END in n:
                out.append(n[self.END])
            for ch in sorted(k for k in n if len(k) == 1 and k != self.END):
                collect(n[ch])
        collect(node)
        return out


def word_search(board, words):
    """Backtracking + trie together. Searching each word independently is
    O(words * cells * 4^len). Putting all words in a trie walks the grid ONCE
    and prunes the moment the path spells a prefix no word has."""
    trie = Trie()
    for w in words:
        trie.insert(w)
    rows, cols = len(board), len(board[0])
    found, visits = set(), [0]

    def walk(r, c, node):
        visits[0] += 1
        ch = board[r][c]
        if ch not in node:
            return                            # PRUNE: dead prefix
        nxt = node[ch]
        if trie.END in nxt:
            found.add(nxt[trie.END])
        board[r][c] = None                    # mark visited in place
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] is not None:
                walk(nr, nc, nxt)
        board[r][c] = ch                      # un-choose
    for r in range(rows):
        for c in range(cols):
            walk(r, c, trie.root)
    return sorted(found), visits[0]


if __name__ == "__main__":
    print("permutations([1,2,3]) :", permutations([1, 2, 3]))
    print("subsets([1,2,3])      :", subsets([1, 2, 3]))

    print()
    res, pruned_calls = combination_sum([2, 3, 6, 7], 7)
    _, unpruned_calls = combination_sum_unpruned([2, 3, 6, 7], 7)
    print("combination_sum([2,3,6,7], 7) :", res)
    print("recursive calls, pruned       :", pruned_calls)
    print("recursive calls, unpruned     :", unpruned_calls)

    print()
    for n in (4, 6, 8):
        count, ex = n_queens(n)
        print(f"n_queens({n}) solutions      : {count}")
    print("first two 8-queens boards (column per row):")
    for b in n_queens(8)[1]:
        print("   ", b)

    print()
    t = Trie()
    for w in ["car", "card", "care", "careful", "cat", "dog"]:
        t.insert(w)
    print("search('car')         :", t.search("car"))
    print("search('ca')          :", t.search("ca"), "(a prefix is not a word)")
    print("starts_with('ca')     :", t.starts_with("ca"))
    print("count_with_prefix(car):", t.count_with_prefix("car"))
    print("count_with_prefix(ca) :", t.count_with_prefix("ca"))
    print("autocomplete('car')   :", t.autocomplete("car"))

    print()
    board = [list("oaan"), list("etae"), list("ihkr"), list("iflv")]
    words = ["oath", "pea", "eat", "rain", "hike"]
    hits, visits = word_search(board, words)
    print("board                 :", ["".join(r) for r in board])
    print("words                 :", words)
    print("found                 :", hits)
    print("cell visits with trie :", visits)

Five details worth defending.

out.append(tuple(path)) copies. path is mutated after the append, so storing a reference stores a list that will be empty by the time you read it. This produces the famous "all my results are identical" or "all my results are empty" bug, and it happens to almost everyone once.

The un-choose must undo everything the choose did. In n_queens, the choose adds to three sets and appends to the board, and the un-choose removes from three sets and pops. Miss one and the search silently loses solutions. Keeping choose and un-choose adjacent and symmetric in the source is a deliberate defence against this.

n_queens prunes with $O(1)$ attack tests, not by scanning the board. Two cells share a diagonal exactly when row - col is equal, and an anti-diagonal exactly when row + col is equal. Maintaining three sets makes the legality check constant time instead of $O(n)$.

combination_sum uses break, not continue. Because the candidates are sorted, once one overshoots the remaining target, every later one does too, so the entire rest of the loop is dead. break kills it; continue walks it. The code includes an unpruned twin purely to measure this.

In the trie, the terminal marker is "$" and the count key is "#count". Both are chosen to be strings that cannot collide with a single character, and autocomplete filters children with len(k) == 1 for the same reason. Using a sentinel that could be a legitimate character is a bug waiting for the input that contains it. A production implementation uses a node class with explicit fields rather than overloading a dict, and that is the better answer if asked to make it production-ready.

Worked example

permutations([1,2,3]) : [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
subsets([1,2,3])      : [(), (3,), (2,), (2, 3), (1,), (1, 3), (1, 2), (1, 2, 3)]

combination_sum([2,3,6,7], 7) : [(2, 2, 3), (7,)]
recursive calls, pruned       : 10
recursive calls, unpruned     : 28

n_queens(4) solutions      : 2
n_queens(6) solutions      : 4
n_queens(8) solutions      : 92
first two 8-queens boards (column per row):
    [0, 4, 7, 5, 2, 6, 1, 3]
    [0, 5, 7, 2, 6, 3, 1, 4]

search('car')         : True
search('ca')          : False (a prefix is not a word)
starts_with('ca')     : True
count_with_prefix(car): 4
count_with_prefix(ca) : 5
autocomplete('car')   : ['car', 'card', 'care', 'careful']

board                 : ['oaan', 'etae', 'ihkr', 'iflv']
words                 : ['oath', 'pea', 'eat', 'rain', 'hike']
found                 : ['eat', 'oath']
cell visits with trie : 47

The pruning measurement is the point of this page. The same search, the same answers, 10 recursive calls with break against 28 with continue. That is a factor of 2.8 on a four-element input with a target of 7. The ratio grows with the input, because the pruned version never enters subtrees whose first step already overshoots, and the number of such subtrees grows combinatorially. Reporting a measured ratio rather than asserting "pruning helps" is what makes the claim worth anything, and instrumenting a call counter takes one line, which is a thing you can do live in an interview if challenged.

The n-queens counts are the standard sequence: 2 for $n=4$, 4 for $n=6$, 92 for $n=8$. If you write this and get 92, you are right; if you get anything else, the un-choose is incomplete. This is a self-checking problem and it is worth knowing that 92 is the number.

search('ca') is False while starts_with('ca') is True, which is the distinction the terminal marker exists to make. A trie node's existence means a prefix was seen, not that a word ends there. Every trie bug involving "it returns words I never inserted" traces back to conflating the two.

count_with_prefix('car') is 4 (car, card, care, careful) and ('ca') is 5 (those four plus cat). The counts are maintained on insert, which makes them $O(1)$ to read. The alternative, walking the subtree on each query, is $O(\text{subtree size})$ and is what people write first.

word_search finds eat and oath in 47 cell visits. Both pea and rain and hike are absent from the grid, and the trie means the search abandoned those paths as soon as the spelled prefix left the trie, rather than exploring four directions to each word's full length. Four separate depth-first searches, one per word, would visit substantially more.

Production evidence

Regex engines backtrack, and it has taken down real systems. PCRE, Python's re, Java's java.util.regex and JavaScript's engine are all backtracking matchers: on a failed alternative they rewind and try the next. A pattern with nested quantifiers such as (a+)+b can take exponential time on a non-matching input, which is the ReDoS vulnerability class. Cloudflare's global outage on 2 July 2019 was caused by a regular expression deployed to their WAF that backtracked catastrophically and drove CPU to saturation across the fleet; their public post-mortem describes the pattern and the fix. The structural answer is a non-backtracking engine (RE2, used by Go's regexp and by several services precisely for this reason), which guarantees linear time by refusing to support backreferences.

SAT solvers are backtracking with industrial-strength pruning. DPLL is backtracking search over variable assignments, with unit propagation and pure literal elimination as pruning rules; modern CDCL solvers add conflict-driven clause learning, which is pruning that remembers why a subtree failed so the same failure is never re-explored. Package managers use them: Dart's pub and several others resolve version constraints with a CDCL-derived algorithm, because dependency resolution is NP-complete and backtracking with learning is what makes it tractable.

Lucene's term dictionary is a compressed trie. Lucene stores the terms of each index segment in a finite state transducer, which is a trie with common suffixes shared as well as common prefixes, and it maps terms to postings-list offsets. That structure is what makes prefix queries, wildcard queries and range queries over terms work without scanning the dictionary, and it is compact enough to hold in memory for a segment.

IP routing is longest prefix match on a trie. A routing table maps address prefixes of varying length to next hops, and forwarding requires the longest matching prefix. The Linux kernel's forwarding information base uses an LC-trie (a level-compressed trie) for IPv4. There is no hash map formulation of this operation, which is the cleanest example of a trie being chosen for capability rather than speed.

Aho-Corasick is a trie with failure links, and it matches many patterns against a text in one pass, in time linear in the text plus the number of matches, independent of the number of patterns. grep -F with many patterns, intrusion detection signature matching, and content scanning all use it. The word_search function on this page is the same idea applied to a grid instead of a string.

The debate

How much should you prune in an interview? There is a real tradeoff and candidates get it wrong in both directions. Aggressive pruning is more code, more chances for an off by one, and harder to explain. My position: write the correct unpruned search first, out loud say "this is exponential and I am going to add pruning", then add exactly the prunes you can justify in one sentence each. In combination_sum that is the sort plus break, which is two lines. In n-queens it is the three attack sets. Do not add a prune you cannot explain, because an interviewer will ask why it is safe, and "safe" means it cannot remove a valid solution, which is a proof obligation.

Trie or hash map for autocomplete? The honest answer is that most production autocomplete is not a bare trie. A trie gives you the candidate set for a prefix, but the product requirement is the top k by popularity, and walking a whole subtree to sort it is too slow when the prefix is short and the subtree is most of the corpus. The production shapes are a trie with the top-k precomputed and cached at each node, or a finite state transducer with weights, or (increasingly) an inverted index over prefix n-grams. Say the trie, then immediately say "with the top-k materialised per node, otherwise a one-character prefix walks the entire corpus." That second clause is the whole difference between a textbook answer and someone who has shipped a typeahead.

When is a trie the wrong structure? When memory matters and keys are long and sparse. A naive trie node with a 26-slot child array wastes enormous space when most children are empty, and the pointer chasing is cache-hostile. The fixes are a radix or Patricia trie (collapse chains of single-child nodes into one edge labelled with a substring), which is what routing tables actually use, or an FST if the set is static. For a large static string set, an FST or a succinct structure will be several times smaller than a pointer trie. If the key set is static and you only need exact lookup, a perfect hash beats both.

Follow-up Q&A

Why does subsets produce them in that order, with the empty set first and (3,) second? Because the recursion excludes before it includes: walk(i+1) without appending runs first. So the first leaf reached excludes everything, then the deepest choice flips first. Order is a consequence of the recursion's shape, not of the problem, and if a specific order is required you either reorder the two recursive calls or sort at the end. Being able to say why the order is what it is, rather than being surprised by it, is the signal.

How do you handle duplicates in the input for permutations or subsets? Sort the input, then within the loop skip any candidate equal to its predecessor that has not been used at this level: if i > 0 and items[i] == items[i-1] and not used[i-1]: continue. The not used[i-1] clause is the subtle part; it distinguishes "the duplicate is being reused at the same tree level" (skip, it makes a duplicate result) from "the duplicate is being used deeper in the same path" (allow, it is a legitimate arrangement). Getting this condition backwards produces either duplicates or missing results, and it is a standard follow-up.

What is the actual complexity of n-queens with your pruning? There is no useful closed form; the number of solutions itself has no formula and is a well studied open problem. The correct answer is to state the upper bound honestly, $O(n!)$ for the unpruned search since each row picks a distinct column, and then say that pruning reduces it by a large but unquantified constant-and-more factor in practice. Interviewers ask this partly to see whether you will invent a bound. Do not.

When would you convert backtracking into dynamic programming? When subtrees repeat, that is, when different decision paths reach the same state and the answer depends only on that state and not on the path. Backtracking over "which coins have I used" has no repetition, so it stays backtracking. Backtracking over "how much target remains" reaches the same remaining value many ways, so memoising on the remaining value converts an exponential search into a polynomial DP. The test is whether the state is smaller than the path, and that sentence is the bridge between this pattern and dynamic programming.

Your trie stores a #count on every node during insert. What breaks if you support delete? The counts have to be decremented along the same path, and nodes whose count reaches zero should be removed or they leak memory and slow later traversals. Deletion in a trie is genuinely fiddly because you can only remove a node when it has no children and is not a word terminal, so you walk back up from the terminal removing while both conditions hold. Most interview tries skip delete for this reason, and saying that explicitly is better than implementing it badly.

How would you find all words within edit distance 1 of a query using the trie? Walk the trie while tracking a small edit budget, allowing at each step a match, a substitution, an insertion or a deletion, and prune any branch whose budget is exhausted. This is the trie version of the Levenshtein automaton, and it is how Lucene's fuzzy query works. The reason it is fast is precisely the pruning: a branch that has already spent its budget and does not match is abandoned near the root rather than at the leaves.

Common misconceptions

"Backtracking and DFS are different algorithms." Backtracking is DFS, over an implicit tree of decisions rather than an explicit graph, plus the undo step and the pruning. If you can already write a DFS, you can write backtracking, and framing it that way makes the pattern much less intimidating.

"Pruning is an optimisation I can add later." For enumeration problems, sometimes. For search problems like n-queens at $n = 20$, or SAT, pruning is the difference between terminating and not, so it is part of the algorithm rather than a tuning pass.

"A trie gives $O(1)$ lookup." It gives $O(m)$ for a key of length $m$, with a pointer dereference and likely a cache miss per character. What is $O(1)$ with respect to is the number of stored keys, and that is the claim to make precisely.

"Regexes are fast." Backtracking regex engines are fast on typical input and catastrophically slow on adversarial input. If a regex ever sees user-supplied input, either use a linear-time engine or bound the execution, and know that this is a documented availability vulnerability class rather than a theoretical one.

Interview delivery note

Before writing any backtracking, say the four parts out loud: "State is X. The choices at each step are Y. The base case is Z. The prune is: if [condition] then no completion of this path can work, so I stop." Naming the prune and its justification in the same breath is the move, because the justification is what proves you have not broken correctness.

The senior-to-staff separator: connecting the pattern to its production failure mode unprompted. A senior candidate writes a correct backtracking search. A staff candidate writes the same code and adds: "Note this is the same machinery as a backtracking regex engine, so the same input-dependent blowup applies. If this ever runs on user-controlled input, I would bound the node count and fail closed rather than let it run, which is essentially the mitigation for ReDoS." Similarly on the trie: "this answers prefix queries, but for autocomplete I would materialise the top k at each node, because a one-character prefix otherwise walks the whole corpus." Both sentences say the same thing about you: you have thought about what happens when this code meets real traffic, which is the thing a staff engineer is hired to do.

The Staff & Team Lead Interview Reference