DevPath
Tracks

Backtracking

Explore choices one at a time, undo them when they fail, and prune whole branches early. Subsets, permutations, and N-Queens.

intermediate45 min#backtracking#recursion#search#pruning

Prerequisites: Recursion

Why it matters

Some problems ask you to build something out of many choices: every arrangement, every valid combination, every way to fill a grid. There is no formula; you have to search. Backtracking is the disciplined way to search. It powers puzzle solvers (Sudoku, N-Queens), combinatorial generators, parsing with alternatives, and constraint solvers. It is also a staple interview topic because it tests whether you can manage state cleanly through recursion.

Intuition

Imagine walking a maze with a ball of string. At each fork you pick a corridor and keep walking. If you hit a dead end, you rewind the string to the last fork and try the next corridor. You never forget what you tried, and you never walk the same path twice.

Backtracking is a depth-first walk over a decision tree. Each level is one decision; each branch is one option. A full path from root to leaf is one complete candidate. The art is cutting off branches that cannot possibly lead to a valid answer, as early as you can.

How it works

Almost every backtracking solution has the same skeleton:

  1. State: a partial solution (path) plus anything needed to check validity.
  2. Base case: if the partial solution is complete, record a copy of it.
  3. Choices: loop over the options available at this step.
  4. Choose, explore, unchoose: apply the option, recurse, then undo it so the next option starts from a clean state.
  5. Prune: skip an option as soon as it violates a constraint.
subsets of [1, 2]  (take or skip each item)

            start
          /       \
     skip 1       take 1
      /   \        /   \
   skip 2 take 2 skip 2 take 2
    []    [2]     [1]   [1,2]

Here is that depth-first walk over the subsets of [1, 2, 3]. Each node is the current path.

+1+2+3+3+2+3+3[][1][1,2][1,2,3][1,3][2][2,3][3]
Start with an empty path. Every node of this tree is one subset: a branch adds a larger item. Recorded: [] (1 subset).
step 1 / 8

Green is the current path, amber is already explored. Each backtrack is the undo step (pop) returning to a parent. All 8 subsets are visited exactly once.

The undo step is what makes it backtracking. Because path is shared and mutated, you must append a copy when you record an answer, or every stored result will end up pointing at the same list.

Pruning is where the savings are. Plain enumeration of N-Queens places one queen per row in any of n columns: n^n boards. Rejecting a square the moment it shares a column or diagonal with an earlier queen cuts the tree enormously. The worst case is still exponential, but the practical work is a tiny fraction.

To see pruning, look for combinations of the distinct numbers 2, 3, 4 (each used at most once, in increasing order) that sum to 6. Each node shows its path and running sum.

+2+3+4+4+3+4+4[] s=02 s=22,3 s=52,3,4 s=92,4 s=63 s=33,4 s=74 s=4
Green is the only valid answer. The faded nodes go over 6, so the search rejects them the moment the sum is exceeded and never explores anything below them. Fewer nodes visited, same answers.

For N-Queens, two squares share a diagonal when row - col is equal (one direction) or row + col is equal (the other). Keeping three sets (columns, both diagonals) makes each check O(1).

A 4 by 4 board shows the same rhythm of place, fail, and undo. Queens are green; amber squares were rejected in that row.

c0c1c2c3
row 0
Q
row 1
row 2
row 3
Row 0: place a queen in column 0.
step 1 / 9

One queen per row, left to right. When a row has no safe square the search steps back and moves an earlier queen. Pruning stops each doomed branch immediately.

OperationTimeNotes
All subsetsO(2^n * n)2^n leaves, copying a path costs up to n
All permutationsO(n! * n)n! leaves
N-Queens (with pruning)ExponentialFar below n^n in practice
Recursion depth / spaceO(n)One frame per decision, excluding output

Code: subsets, permutations, N-Queens

def subsets(nums):
    out, path = [], []
    def go(i):
        if i == len(nums):
            out.append(path[:])      # copy, path keeps mutating
            return
        go(i + 1)                    # choice 1: skip nums[i]
        path.append(nums[i])         # choice 2: take it
        go(i + 1)
        path.pop()                   # undo
    go(0)
    return out
 
def permutations(nums):
    out, path, used = [], [], [False] * len(nums)
    def go():
        if len(path) == len(nums):
            out.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            go()
            path.pop()
            used[i] = False
    go()
    return out
 
def count_queens(n):
    cols, diag1, diag2 = set(), set(), set()
    def place(row):
        if row == n:
            return 1
        total = 0
        for c in range(n):
            if c in cols or row - c in diag1 or row + c in diag2:
                continue             # prune: square is attacked
            cols.add(c); diag1.add(row - c); diag2.add(row + c)
            total += place(row + 1)
            cols.remove(c); diag1.remove(row - c); diag2.remove(row + c)
        return total
    return place(0)
 
print(len(subsets([1, 2, 3])), " ".join(map(str, subsets([1, 2, 3])[-1])))
print(" ".join("".join(map(str, p)) for p in permutations([1, 2, 3])))
print(count_queens(4), count_queens(6), count_queens(8))

Both versions print three lines: 8 1 2 3 (eight subsets, the last of which is 1 2 3), then 123 132 213 231 312 321, then 2 4 92 (the number of N-Queens solutions for boards of size 4, 6 and 8).

Common pitfalls

  • Forgetting to copy: out.append(path) stores a reference. Use path[:] in Python or [...path] in JavaScript.
  • Forgetting to undo: every mutation before the recursive call needs an opposite after it (pop the item, clear the flag, remove from the set).
  • Duplicates in the input: with repeated values you will produce repeated results. Sort first, and skip an option equal to the previous one at the same level (when that previous one was not used on this path).
  • Pruning too late: checking validity only at the leaf throws away the main benefit. Check as soon as a choice is made.
  • Exploding output: subsets and permutations grow exponentially and factorially. 20 items already mean over a million subsets; the algorithm is right, the problem is just big.

Practice

Generate balanced parentheses easy

Hint

You can add an open paren while you have some left, and a close paren only if it would not exceed the opens so far.

Show solution

Track opens and closes used. If opens < n, add (. If closes < opens, add ). When the string length is 2n, record it. The two conditions prune every invalid prefix, so you only ever build valid strings. The count is the Catalan number.

Combination sum medium

Hint

Pass a start index so you do not generate the same combination in a different order. Prune when the remaining target goes negative.

Show solution

For each call, loop i from start to n - 1. If candidates[i] > remaining, skip it (and break if the list is sorted). Otherwise append it, recurse with the same i (reuse allowed) and remaining - candidates[i], then pop. Record the path when remaining == 0.

Word search in a grid medium

Hint

Mark the current cell visited so you cannot reuse it, and unmark on the way back.

Show solution

For each starting cell, run DFS matching the word one character at a time. Temporarily replace the cell with a marker, try the four neighbours, then restore the cell. Return true as soon as the whole word is matched. Pruning on the first mismatched character keeps it fast; worst case is about cells * 3^len.

Sudoku solver hard

Hint

Pick the next empty cell, try digits 1 to 9 that fit row, column and box, and undo on failure. Which cell should you pick first?

Show solution

Keep sets for each row, column, and 3 by 3 box. For an empty cell, try every digit not present in its three sets; place it, recurse, and clear it if the recursion fails. Choosing the empty cell with the fewest legal digits first (a heuristic called most constrained variable) prunes dramatically more than scanning in order.

Interview questions

  1. How do you know a problem needs backtracking? It asks for all solutions, or for any solution under constraints, and the input is small (often n up to about 20 or a small grid).
  2. What is the difference between choosing, exploring, and unchoosing? Apply a decision to the shared state, recurse to handle the rest, then reverse the decision so siblings see the original state.
  3. How do you avoid duplicate results? Sort the input and skip an element equal to its predecessor at the same depth, or pass a start index for combinations.
  4. What is the time complexity of permutations? O(n! * n): n! leaves and each copy costs n.

Interviewers look for: a clear skeleton, undoing state correctly, copying results, and proposing a pruning rule instead of brute-force checking at the leaves.

Quick check

In the subsets code, why do we append a copy of path instead of path itself?

Finished this lesson?

Further resources

Related lessons