Backtracking explained: the choose, check, recurse, undo pattern

In this article

1. Before you start
2. Why interviewers ask this
3. Backtracking from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

Why interviewers ask this

Backtracking is the standard tool for "generate all" and "find any valid" problems, and a wrong version still runs without raising an error. That makes it a favourite probe in the coding interviews round: permutations, subsets, N-Queens, Sudoku, word search and combination sums all share one template. A weak answer writes a loop that generates everything and filters afterwards, which is slow, or writes the recursion and forgets the undo, which returns wrong output. A strong answer states the choice at each level, the rule that prunes, the undo, and the cost. The follow-up is nearly always "how many nodes does this visit?", so this page measures that number.

Backtracking from first principles

Backtracking

Backtracking is an algorithm that builds a solution incrementally, one small piece at a time (Erickson, Algorithms, chapter 2), and abandons a candidate as soon as it cannot be completed into a valid solution (Wikipedia, Backtracking, last edited 19 August 2026).

Pruning

Pruning is the act of skipping a whole branch of the search tree because the partial solution at its root already breaks a rule, so none of the solutions below it are ever generated.

Search tree

A search tree is the tree whose nodes are the partial solutions and whose edges are the choices, so that each leaf is a complete candidate and the root is the empty one.

In plain words

Backtracking is how you solve a maze by walking it. At every fork you pick a path. If you reach a dead end, you walk back to the last fork and try another path. You never explore beyond a wall. The analogy breaks in one place: in a maze you remember where you are by standing there, while in code you must undo your change to the shared state yourself, because the computer does not walk back for you. Stated precisely, backtracking tries a choice, explores the consequences, and then removes the choice before trying the next one.

The two running examples are small. Permutations of the list 1, 2, 3 show the template, and the N-Queens puzzle, which asks you to place n queens on an n-by-n chessboard so that no two attack each other, shows why pruning matters.

Step 1: Define the choices and the rule

The first step decides what one decision is and what makes a partial solution invalid. Erickson describes the pattern as making exactly one decision in each recursive call, with the choice consistent with all previous decisions (Erickson, chapter 2). For permutations the decision is which unused item goes in the next position, and the rule is that each item is used once. For N-Queens the decision is the column of the queen in the next row, and the rule is that no earlier queen shares its column or diagonal. Write both in one sentence before any code. What you now know: the tree has one level per decision.

Step 2: Choose one option and prune if the rule fails

The second step loops over the options for the current decision and rejects any that break the rule. The input is the current partial solution; the output is the list of options that survive. In N-Queens, for each column in the current row, skip it if a column or diagonal is already attacked. That skip is pruning: every board that would have started with that placement is never built. Check the rule before recursing, not at the leaf, because early rejection is the whole benefit and a rule that is checked late saves nothing. Keep the check cheap, such as a set lookup. What you now know: pruning removes the subtree below a bad choice.

Step 3: Recurse, then undo the choice

The third step makes the choice, explores deeper with a recursive call, and then reverses the choice. The input is the surviving option; the output is the shared state restored exactly as it was. In permutations, mark the item used and append it, call the function, then remove it and mark it unused. The undo is what lets the next loop iteration start from the same state. Without it, the earlier choice stays in place: when the undo is deleted from the permutation code, only 1 of the 6 permutations of 1, 2, 3 comes back.¹ What you now know: every change before the call has a matching reversal after it.

Step 4: Record a copy when the solution is complete

The fourth step stores a finished solution at the leaf, and it must store a copy. The input is the full path; the output is one new list in the results. The path list is reused and emptied as the search walks back, so storing the path itself stores a reference that later changes. In the run, storing the path without copying returned six empty lists instead of six permutations.¹ Copy it with a slice or a constructor call, and do this only at a complete solution, never in the middle of the search. What you now know: results hold snapshots, not the live path.

1 · Choices and rule2 · Choose and prune3 · Recurse, undo4 · Record a copyReplay

Step-by-step description

1. Decide what one decision is.
2. Skip options that break the rule.
3. Reverse the choice after the call.
4. Store a snapshot, not the path.

• Without the undo, only 1 of the 6 permutations of 1, 2, 3 comes back.
• Storing the path without copying it returned six empty lists instead of six permutations.

Worked example

Both examples were run in Python 3.12.12.¹ The search tree for permutations of 1, 2, 3 has 16 nodes (1 root, 3 choices, 6 two-item prefixes and 6 full permutations) and 6 results, starting with 1, 2, 3 then 1, 3, 2, then 2, 1, 3. For N-Queens, the solution counts for n from 4 to 8 are 2, 10, 4, 40 and 92, which match the On-Line Encyclopedia of Integer Sequences (OEIS) entry A000170. The new number is the cost: for 8 queens, backtracking visits 2,057 nodes, against 109,601 nodes in the permutation tree that only forbids a repeated column, and against 4,426,165,368 ways to choose 8 squares of 64.¹

The template below is the version that produced these counts for permutations; it shows all four steps.

def permutations(items):
    results, path, used = [], [], [False] * len(items)

    def go():
        if len(path) == len(items):
            results.append(path[:])      # step 4: store a copy
            return
        for i, x in enumerate(items):
            if used[i]:
                continue                 # steps 1-2: the rule prunes
            used[i] = True               # step 2: choose
            path.append(x)
            go()                         # step 3: recurse
            path.pop()                   # step 3: undo
            used[i] = False
    go()
    return results

Text description of the diagram

• The share falls as the board grows: 26.2 percent of the tree at n = 4, 1.9 percent at n = 8 and 0.4 percent at n = 10.
• Backtracking is still exponential in the worst case.

The share falls as the board grows: 26.2 percent of the tree at n = 4, 1.9 percent at n = 8 and 0.4 percent at n = 10.¹ The tree is still huge in absolute terms, and backtracking is still exponential in the worst case. Pruning shrinks the tree by a factor that grows with n (about 4 times at n = 4, 53 at n = 8 and 278 at n = 10),¹ but the node count still grows exponentially, so the worst case stays exponential.

Trade-offs and edge cases

Backtracking is exhaustive search made cheaper by pruning, so its worst case stays exponential in the number of decisions. Wikipedia describes the idea the same way: a candidate is dropped once it cannot lead to a valid result, and the whole subtree below it is skipped (Wikipedia, last edited 19 August 2026). Three cases decide most interview follow-ups.

First, ordering matters. Try the most constrained decision first, such as the Sudoku cell with the fewest legal digits, because early failures prune more. Second, repeated input items create repeated results; sort the input and skip an item equal to the previous one at the same level. Third, recursion depth: Python's default recursion limit was 1000 in the run, so a problem with thousands of decisions needs an iterative form or a raised limit.¹

Backtracking is not the right tool when subproblems repeat. If the same partial state can be reached by different paths and only the best value or the count is needed, dynamic programming, which stores the answer to each subproblem, is faster. Backtracking is the right tool when you must list the solutions or find any one under constraints. Graph problems with a different structure, such as ordering tasks, use other algorithms; see topological sort and cycle detection in a directed graph.

Text description of the diagram

• Without the undo, only 1 of the 6 permutations of 1, 2, 3 comes back.
• Without the copy, six empty lists come back; checking diagonals only at the leaf, 8 queens visits 109,601 nodes instead of 2,057.

How to answer it in an interview

Say it in this order: the decision, the rule, the undo, the copy, the cost.

Common mistakes

1. Forgetting the undo. (wrong) "I append, recurse, and move on." (right) "I append, recurse, then pop, so the state is restored."
2. Storing the live path. (wrong) results.append(path). (right) results.append(path[:]), a copy.
3. Checking the rule only at the leaf. (wrong) "I build every full candidate and filter." (right) "I check before recursing so a bad choice prunes its subtree."
4. Ignoring repeated input items. (wrong) Running the template on 1, 1, 2 and returning duplicate results. (right) Sort and skip an equal neighbour at the same level.
5. Claiming it is polynomial. (wrong) "Pruning makes it fast." (right) "Pruning can shrink the tree enormously, but the worst case is still exponential."

Follow-up questions

Given a grid of letters and a dictionary, how do you find every word formed from adjacent letters?

Start a search from every cell. At each step, extend the current word by one adjacent unused letter, mark the cell as visited, recurse, then unmark it. Prune as soon as the current letters are not the beginning of any dictionary word, which a trie (a tree of letter prefixes) answers quickly, and record a word when it is complete.

How do you avoid duplicate results when the input has repeated items?

Sort the input first. At each level, skip an item that equals the previous item at the same level, so a value is tried only once per position. For permutations of 1, 1, 2 this returns three distinct results instead of six.

What is the time complexity of backtracking?

It is bounded by the number of nodes in the search tree times the work per node. For permutations of n items there are n! leaves, and for 8 queens the run visited 2,057 nodes where the permutation tree has 109,601 and a tree with no pruning at all has 19,173,961.¹ Brute force builds every complete candidate and tests it, whereas backtracking tests partial candidates; dynamic programming instead reuses repeated subproblems and suits counting. State the worst case honestly: exponential.

How would you list every letter combination a phone number could spell?

Each digit from 2 to 9 maps to three or four letters. The decision is which letter to place for the next digit, there is no rule to fail, and the recursion ends when every digit has a letter. The cost is at most 4 to the power of n for n digits, because the digits 7 and 9 have four letters, so say that bound out loud.

How would you split an array into K groups with equal sums, and how do you prune?

Check first that the total divides by K, then try to fill one group at a time up to the target sum. Prune when an item would push a group over the target, sort the items largest first so failures appear early, and skip an item equal to one that has just failed in the same group. The worst case stays exponential.

What if the board is ten by ten instead of eight by eight?

The solutions grow from 92 to 724 (OEIS A000170), and the run visited 35,539 nodes against 9,864,101 in the permutation tree, so about 0.4 percent.¹ Related reading: longest substring without repeating characters, defaultdict, hash map against hash set and interview loops.

Sources

1. Algorithms, chapter 2: Backtracking — Jeff Erickson, University of Illinois (PDF dated June 2019), 16 Jun 2019
2. A000170, Number of ways of placing n nonattacking queens on an n X n board — The On-Line Encyclopedia of Integer Sequences (page read 2026-10-24), 24 Oct 2026
3. Backtracking — Wikipedia (last edited 19 August 2026), 19 Aug 2026