Backtracking

coreCommon atGoogleMetaAmazonMicrosoftRead firstRecursionDepth-first searchPractise in the Sandbox →

Backtracking is a depth-first walk over a tree of decisions. At each node you choose an option, explore the rest recursively, then un-choose it so the shared state is exactly as before. The big win is pruning: reject a partial solution the moment it breaks a rule, and its whole subtree disappears. The worst case stays exponential (often O(bᵈ) or O(n!)), but good pruning makes real inputs fast.

The idea in plain words

Think of a combination lock where you can feel when a digit is wrong. You set digit 1, then digit 2. If digit 2 clicks wrong, you don’t bother trying digits 3 and 4: you change digit 2. When digit 2 runs out of options, you step back and change digit 1.

Three moves, every time:

1. Choose: commit to one option for the current decision. Mutate the shared state (add to a path, mark a cell used).
2. Explore: recurse to make the next decision.
3. Un-choose: reverse exactly what you did in step 1, then try the next option.

And one rule that makes it fast:

• Prune before you choose. If the partial solution already violates a constraint, or can’t possibly beat the best answer found so far, skip that option entirely. Everything below it in the tree never gets built.

Brute force generates complete candidates and checks them at the end. Backtracking checks as it builds, so a bad choice at depth 2 costs one check, not millions.

See it

N-Queens: place n queens on an n × n board so no two share a row, column or diagonal. Each row is one decision (which column?), so the board’s rows are the levels of the decision tree on the right. Step through and watch a queen get placed (choose), the search move to the next row (explore), and the queen get lifted again (un-choose). Red tries are pruned on the spot.

Choose, explore, un-choose

step through

row = depth in the tree

placements0

pruned0

backtracks0

solutions0

current choiceon the current path / attackerpruned try / dead branchleads to a solution

Tree nodes are labelled with the column chosen at that row; ✕k = columns pruned there.

Place 4 queens, one per row, so none share a column or diagonal. Decide row 0 first, then row 1, and so on: each decision is one level of the tree.

↺◀▶ Play▶1 / 84

Notice how few nodes the tree has. On a 4 × 4 board there are 4⁴ = 256 ways to put one queen per row, but backtracking only builds 17 partial boards. The gap grows fast:

Candidates examined: brute force vs pruning

drag the slider

n = 8

Any square for each queen: C(n², n)

4.43 × 10^9

One per row, check at the end: nⁿ

1.68 × 10^7

One per row and column: n!

40,320

Backtracking, prune on conflict

2,057

Bars use a log scale. For n = 8 there are 92 solutions. Backtracking visits 2,057 partial boards, because it abandons a placement the moment two queens clash instead of finishing it first.

When to reach for it

The problem says…	Why backtracking fits
“generate all subsets / permutations / combinations / arrangements”	The output itself is exponential; walk the decision tree and emit leaves.
“find any assignment that satisfies these constraints” (puzzles, scheduling, colouring)	Prune violating partial assignments; stop at the first full one.
“does a word / path exist” tracing through a grid without reusing cells	DFS where “visited” is undone on the way back.
“split / partition the input into pieces such that…”	Each cut position is a decision.
small n (≤ ~20 for subsets, ≤ ~10 for permutations) and no obvious structure	Exponential is acceptable; a cleverer method may not exist.

Counting or optimising? Check for overlap first

If you only need a count or the best value, and the same sub-question (same remaining input, same state) gets asked repeatedly, add memoization or switch to dynamic programming. Backtracking is for when you need the actual solutions, or when states rarely repeat.

How it works

1. Prune. For each option at this decision, skip it if it breaks a constraint given the choices so far.
2. Choose. Apply the option to the shared state.
3. Explore. Recurse to the next decision. If you only need one answer, return as soon as the recursion reports success.
4. Base case and un-choose. When every decision is made, record the answer (a copy of the state). Back in the loop, undo step 2 exactly before trying the next option.

N-Queens keeps three sets so the conflict check is O(1): occupied columns, r − c for one diagonal direction, and r + c for the other.

Python

n_queens.py

def n_queens(n: int) -> list[list[int]]:
    """All ways to place n non-attacking queens; each answer lists the queen's column per row."""
    cols: set[int] = set()
    diag: set[int] = set()       # r - c is constant along a "\" diagonal
    anti: set[int] = set()       # r + c is constant along a "/" diagonal
    placed: list[int] = []
    out: list[list[int]] = []

    def place(r: int) -> None:
        if r == n:                                   # 4. every row filled: record a COPY
            out.append(placed.copy())
            return
        for c in range(n):
            if c in cols or r - c in diag or r + c in anti:
                continue                             # 1. prune: this branch can't succeed
            cols.add(c); diag.add(r - c); anti.add(r + c); placed.append(c)   # 2. choose
            place(r + 1)                                                    # 3. explore
            cols.remove(c); diag.remove(r - c); anti.remove(r + c); placed.pop()  # un-choose

    place(0)
    return out


if __name__ == "__main__":
    assert n_queens(4) == [[1, 3, 0, 2], [2, 0, 3, 1]]
    assert len(n_queens(6)) == 4
    assert len(n_queens(8)) == 92
    assert n_queens(2) == [] and n_queens(3) == []
    print("ok")

TypeScript

n_queens.ts

import assert from "node:assert/strict";

/** All ways to place n non-attacking queens; each answer lists the queen's column per row. */
export function nQueens(n: number): number[][] {
  const cols = new Set<number>();
  const diag = new Set<number>(); // r - c is constant along a "\" diagonal
  const anti = new Set<number>(); // r + c is constant along a "/" diagonal
  const placed: number[] = [];
  const out: number[][] = [];
  const place = (r: number): void => {
    if (r === n) { // 4. every row filled: record a COPY
      out.push([...placed]);
      return;
    }
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || diag.has(r - c) || anti.has(r + c)) continue; // 1. prune
      cols.add(c); diag.add(r - c); anti.add(r + c); placed.push(c); // 2. choose
      place(r + 1); // 3. explore
      cols.delete(c); diag.delete(r - c); anti.delete(r + c); placed.pop(); // un-choose
    }
  };
  place(0);
  return out;
}

assert.deepEqual(nQueens(4), [[1, 3, 0, 2], [2, 0, 3, 1]]);
assert.equal(nQueens(6).length, 4);
assert.equal(nQueens(8).length, 92);
assert.deepEqual(nQueens(3), []);
console.log("ok");

C#

n_queens.cs

var four = NQueens(4);
if (four.Count != 2 || string.Join(",", four[0]) != "1,3,0,2") throw new Exception("n=4");
if (NQueens(8).Count != 92) throw new Exception("n=8");
if (NQueens(3).Count != 0) throw new Exception("n=3");
Console.WriteLine("ok");

// All ways to place n non-attacking queens; each answer lists the queen's column per row.
static List<int[]> NQueens(int n)
{
    var cols = new HashSet<int>();
    var diag = new HashSet<int>();   // r - c is constant along a "\" diagonal
    var anti = new HashSet<int>();   // r + c is constant along a "/" diagonal
    var placed = new List<int>();
    var output = new List<int[]>();
    void Place(int r)
    {
        if (r == n) { output.Add(placed.ToArray()); return; }        // 4. record a COPY
        for (int c = 0; c < n; c++)
        {
            if (cols.Contains(c) || diag.Contains(r - c) || anti.Contains(r + c)) continue; // 1. prune
            cols.Add(c); diag.Add(r - c); anti.Add(r + c); placed.Add(c);               // 2. choose
            Place(r + 1);                                                                // 3. explore
            cols.Remove(c); diag.Remove(r - c); anti.Remove(r + c); placed.RemoveAt(placed.Count - 1); // un-choose
        }
    }
    Place(0);
    return output;
}

The same skeleton finds one valid assignment and stops. Here: colour a graph’s nodes with k colours so no edge joins two nodes of the same colour.

Python

color_graph.py

def color_graph(adj: list[list[int]], k: int) -> list[int] | None:
    """Give each node a colour 0..k-1 so neighbours differ, or None if impossible."""
    n = len(adj)
    color = [-1] * n                                 # -1 = not decided yet

    def assign(u: int) -> bool:
        if u == n:                                   # every node coloured
            return True
        for c in range(k):
            if any(color[v] == c for v in adj[u]):   # 1. prune: clashes with a neighbour
                continue
            color[u] = c                             # 2. choose
            if assign(u + 1):                        # 3. explore; stop at the first success
                return True
            color[u] = -1                            # 4. un-choose before trying the next colour
        return False                                 # no colour works: caller must backtrack

    return color if assign(0) else None


if __name__ == "__main__":
    triangle = [[1, 2], [0, 2], [0, 1]]
    assert color_graph(triangle, 2) is None
    assert color_graph(triangle, 3) == [0, 1, 2]
    square = [[1, 3], [0, 2], [1, 3], [0, 2]]        # even cycle: 2 colours suffice
    assert color_graph(square, 2) == [0, 1, 0, 1]
    print("ok")

TypeScript

color_graph.ts

import assert from "node:assert/strict";

/** Give each node a colour 0..k-1 so neighbours differ, or null if impossible. */
export function colorGraph(adj: number[][], k: number): number[] | null {
  const n = adj.length;
  const color = new Array<number>(n).fill(-1); // -1 = not decided yet
  const assign = (u: number): boolean => {
    if (u === n) return true; // every node coloured
    for (let c = 0; c < k; c++) {
      if (adj[u].some((v) => color[v] === c)) continue; // 1. prune: clashes with a neighbour
      color[u] = c; // 2. choose
      if (assign(u + 1)) return true; // 3. explore; stop at the first success
      color[u] = -1; // 4. un-choose before trying the next colour
    }
    return false; // no colour works: caller must backtrack
  };
  return assign(0) ? color : null;
}

const triangle = [[1, 2], [0, 2], [0, 1]];
assert.equal(colorGraph(triangle, 2), null);
assert.deepEqual(colorGraph(triangle, 3), [0, 1, 2]);
const square = [[1, 3], [0, 2], [1, 3], [0, 2]]; // even cycle: 2 colours suffice
assert.deepEqual(colorGraph(square, 2), [0, 1, 0, 1]);
console.log("ok");

C#

color_graph.cs

int[][] triangle = [[1, 2], [0, 2], [0, 1]];
if (ColorGraph(triangle, 2) is not null) throw new Exception("triangle needs 3 colours");
if (string.Join(",", ColorGraph(triangle, 3)!) != "0,1,2") throw new Exception("triangle k=3");
int[][] square = [[1, 3], [0, 2], [1, 3], [0, 2]]; // even cycle: 2 colours suffice
if (string.Join(",", ColorGraph(square, 2)!) != "0,1,0,1") throw new Exception("square");
Console.WriteLine("ok");

// Give each node a colour 0..k-1 so neighbours differ, or null if impossible.
static int[]? ColorGraph(int[][] adj, int k)
{
    int n = adj.Length;
    var color = Enumerable.Repeat(-1, n).ToArray();   // -1 = not decided yet
    bool Assign(int u)
    {
        if (u == n) return true;                      // every node coloured
        for (int c = 0; c < k; c++)
        {
            if (adj[u].Any(v => color[v] == c)) continue; // 1. prune: clashes with a neighbour
            color[u] = c;                             // 2. choose
            if (Assign(u + 1)) return true;           // 3. explore; stop at the first success
            color[u] = -1;                            // 4. un-choose before the next colour
        }
        return false;                                 // no colour works: caller backtracks
    }
    return Assign(0) ? color : null;
}

Two ways to shape the tree for subsets

For “pick a subset of [a, b, c]” there are two standard trees. Both are worth knowing:

Shape	Each node decides	Branching	Leaves
Include / exclude	“is item i in or out?”	2	2ⁿ, every leaf is a subset
Pick the next item	“which item (with index > last pick) comes next?”	shrinking	every node is a subset

The second shape (loop for j in range(start, n), recurse with start = j + 1) is what makes combinations come out in order without duplicates.

What it costs

Search space	Leaves	Typical total time
Subsets of n items	2ⁿ	O(n · 2ⁿ) including copying each answer
Permutations of n items	n!	O(n · n!)
k-combinations of n	C(n, k)	O(k · C(n, k))
n decisions, b options each	bⁿ	O(bⁿ) worst case
N-Queens	< n!	far below n! thanks to pruning; 8-queens visits about 2,000 partial boards

Two rules of thumb:

• The output bounds the time from below. If you must return all 2ⁿ subsets, nothing beats Ω(n · 2ⁿ). Say so; don’t try to “optimise” it away.
• Extra space is the recursion depth (number of decisions) plus the current partial solution: O(n), not counting the output.

Pruning doesn’t change the worst-case bound in general, but in practice it can cut the work by orders of magnitude. Order decisions so that failures show up early: the most constrained choice first (“fail-first”).

Variations you’ll meet

• Constraint satisfaction (Sudoku, crosswords, colouring): choose the most constrained cell next and keep per-row/column/box sets for O(1) checks.
• Branch and bound: when optimising, prune any branch whose optimistic bound can’t beat the best answer so far.
• Grid path search with “used” marks: mark a cell before recursing, unmark after. Undo is what lets other paths reuse the cell.
• Duplicates in the input: generating everything and deduplicating at the end wastes work and memory. Ask yourself which branches of the tree produce the same output, and prevent them from being built.
• Bitmasks for state: for n ≤ ~20, a bitmask of used items or attacked columns makes choose/un-choose a single XOR. See bit manipulation.

Pitfalls

• Appending the live list (out.append(path)) instead of a copy. Every saved answer then points to the same list, which ends up empty. Use path.copy(), [...path], path.ToArray().
• Incomplete undo. Every mutation in “choose” needs its exact inverse in “un-choose”. Missing one corrupts every later branch silently.
• Pruning too late. Checking constraints only at the leaves turns backtracking back into brute force.
• Wrong loop start for combinations. Starting at 0 instead of start produces both [a, b] and [b, a].
• Not stopping when one answer is enough. Propagate a True up and return.
• Recursion depth is rarely a problem here (depth = number of decisions), but the running time is. State the exponential bound up front.

In the interview

• Ask: all solutions, any solution, a count, or the best one? Can the input contain duplicates? Does order matter in the output? How large is n?
• Draw the decision tree for a tiny input before coding. Say what one level decides and what the branching factor is.
• Name the three moves out loud: “choose, explore, un-choose”, and point at the line that undoes each mutation.
• Give the complexity as output size × cost per output, and explain where you prune.
• Expected follow-ups: handle duplicates, return only the count (memoize?), add a constraint that enables more pruning, or switch the state to a bitmask for speed.

Check yourself

Check yourself

pick one

Your subsets function returns a list of empty lists. The recursion looks right. What's the most likely bug?

AThe base case is wrongBIt appends the shared path list itself, not a copy; un-choose later empties itCThe loop should start at 1DPython recursion limit

Check yourself

pick one

In N-Queens you check conflicts only after all n queens are placed. What have you built?

ABacktracking with pruningBBrute force over all n^n placements: the tree is never cut earlyCDynamic programming

Check yourself

pick one

You need the NUMBER of ways to climb n stairs taking 1 or 2 steps. Is backtracking the right tool?

AYes, enumerate every way and count themBNo: the same sub-question (ways from step i) repeats, so memoize or use DP for O(n)CYes, but only with pruning

Practice on your own

These are classic textbook exercises, not gym questions:

• Count N-Queens solutions for n = 1..10 and compare with the known sequence 1, 0, 0, 2, 10, 4, 40, 92, 352, 724.
• Solve a Sudoku puzzle; then speed it up by always filling the cell with the fewest candidates.
• List all k-combinations of the numbers 1..n.
• Generate every way to split a string into palindromic pieces.
• Restore all valid IPv4 addresses from a string of digits.

Go deeper

• Skiena, The Algorithm Design Manual, chapter “Combinatorial Search”: backtracking, pruning and the subset/permutation construction templates.
• Knuth, The Art of Computer Programming Vol. 4B, “Backtrack programming” (and his Dancing Links paper for exact cover).
• Wikipedia: Eight queens puzzle, for solution counts and history.
• cp-algorithms: Generating all K-combinations.

Related

RecursionBase cases, the call stack, and trusting the recursive call.

Depth-first searchBacktracking is DFS over an implicit tree of choices.

MemoizationWhen sub-questions repeat, cache instead of re-exploring.

Bit manipulationBitmask state for fast choose and un-choose.