On this page

Recursion & Backtracking

Recursion is a function calling itself with a smaller version of the same problem. Backtracking is recursion with a purpose: systematically explore all possible solutions by making a choice, recursing, then undoing the choice (backtracking) when it leads to a dead end. If dynamic programming is "recursion without redundancy," backtracking is "brute force with early termination." It is the right tool when you need to enumerate or find all valid configurations.

This is the first technique lesson of Module 5 (Paradigms). It assumes you are comfortable with the call stack and with proofs by induction from Recursion & Mathematical Induction, and with Big-O from Complexity Analysis. By the end you will be able to write the three core templates (subsets, combinations, permutations) from memory, handle duplicate inputs without producing duplicate answers, prune a search tree in three different ways, count N-Queens solutions with bitmasks, and solve hard Sudoku puzzles in a fraction of a second.

Why this exists

Many problems have no clever formula. "List every way to split this string into palindromes." "Place 8 queens so none attack each other." "Fill this Sudoku." "Does this boolean formula have a satisfying assignment?" The only general method is to search: try a choice, see where it leads, and try something else if it fails.

The naive way to search is to generate every complete candidate and test each one. For 8 queens with one queen per row, that is boards. Backtracking builds candidates one decision at a time and checks the rules after every decision. The moment a partial candidate breaks a rule, it abandons that candidate and every completion of it at once. With that single change, 8-Queens needs only 2,057 recursive calls (measured below), not 16.7 million board checks.

The idea is old. D. H. Lehmer coined the word "backtrack" in the 1950s, and R. J. Walker described it as a general technique in 1960. Golomb and Baumert's 1965 paper "Backtrack Programming" gave the template we still use. Knuth's The Art of Computer Programming, Volume 4B (2022), spends a whole section on it. Today it runs inside SAT solvers, regex engines, package-manager resolvers and constraint solvers (see Real-world uses).

Pattern triggers

If the problem says or has…Think of…
"return all subsets / combinations / permutations"One of the three templates below
"all unique …" and the input may contain repeatsSort first, then skip equal siblings
"find all ways to split / partition / segment a string"Cut-point backtracking (palindrome partitioning, word break II)
"place pieces so that none conflict" (queens, knights, colours)Constraint satisfaction: one decision per row/variable, sets or bitmasks for conflicts
"fill the grid so every row/column/box…"Sudoku-style search with candidate sets and MRV
"does a path spelling this word exist in the grid"Grid DFS with mark-and-restore
"generate all valid strings" with a balance ruleBuild left to right, prune on the rule (parentheses)
– and "all" or "any valid"Exponential search is affordable: ,
"count the ways" or "min/max" with overlapping subproblemsProbably DP instead; backtracking + memo = DP
"any assignment that satisfies these clauses"SAT-style search: propagation + backtracking (DPLL)

The meta-trigger: the answer is a sequence of choices, each choice has a small number of options, and you can tell early that a partial sequence is hopeless.

Recursion Fundamentals

The Call Stack

Every recursive call creates a new stack frame containing the function's local variables, parameters, and return address. The stack frames pile up until a base case is reached, then unwind as each call returns.

graph TD
    subgraph "Call Stack for factorial(4)"
        A["factorial(4)<br/>4 * factorial(3)"] --> B["factorial(3)<br/>3 * factorial(2)"]
        B --> C["factorial(2)<br/>2 * factorial(1)"]
        C --> D["factorial(1)<br/>return 1 ← base case"]
    end

TypeScript:

function factorial(n: number): number {
  if (n <= 1) return 1; // base case
  return n * factorial(n - 1); // recursive case
}

Python:

def factorial(n: int) -> int:
    if n <= 1:
        return 1  # base case
    return n * factorial(n - 1)  # recursive case

Anatomy of a Recursive Function

Every well-formed recursive function has:

  1. Base case(s): When to stop recursing. Without this, you get infinite recursion and a stack overflow.
  2. Recursive case(s): Break the problem into smaller subproblems and recurse.
  3. Progress toward base case: Each recursive call must move closer to the base case.

DANGER

Stack overflow is the #1 risk of recursion. Python has a default recursion limit of 1000. TypeScript/JavaScript depends on the engine (typically ~10,000 frames). For deep recursion, convert to iteration or increase the limit.

import sys
sys.setrecursionlimit(10000)  # use with caution

Recursion vs Iteration

Every recursive algorithm can be converted to an iterative one using an explicit stack. The choice between them is about clarity and constraints:

AspectRecursionIteration
ReadabilityOften clearer for tree/graph problemsClearer for simple loops
Memory stack frames where = depth or explicit stack
Stack overflow riskYesNo
PerformanceFunction call overheadSlightly faster
Tail call optimizationSome languages (not JS/Python)N/A

Recursion refresher

If frames, base cases or "trust the recursive call" still feel shaky, read Recursion & Mathematical Induction first. Backtracking is just recursion where each call also changes shared state on the way down and restores it on the way up.

Intuition & first principles

Decisions, partial solutions and the state-space tree

Picture packing for a trip with three items: a jacket (1), a book (2) and a camera (3). Which sets of items could you pack? You decide one item at a time. "Jacket: yes or no? Book: yes or no?" Every sequence of decisions is a path from a starting point, and the possible paths branch like a tree.

Three words are worth defining now:

  • A partial solution (or partial candidate) is the list of decisions made so far, for example "jacket yes, book no".
  • The state-space tree (or recursion tree) has one node per partial solution. The root is "no decisions yet". The children of a node are the partial solutions you get by making one more decision.
  • A leaf is a node where no more decisions are possible. Some leaves are solutions. Some are dead ends.

Backtracking is a depth-first walk of that tree. It goes down one branch as far as it can, records any solution it meets, then climbs back up one level ("backtracks") and tries the next branch. It never builds the tree in memory. The tree exists only as the pattern of calls over time; at any moment, memory holds one root-to-node path.

Why "undo" is the heart of it

The walk keeps one shared partial solution, usually a list called path. Going down an edge appends a choice. Coming back up must remove it, so that the sibling branch starts from exactly the state its parent had. That is the choose → explore → unchoose rhythm:

  1. Choose: change the shared state (append to path, mark a column as used, write a digit into a cell).
  2. Explore: recurse to handle the rest of the decisions.
  3. Unchoose: reverse step 1 exactly, so the state is as it was before.

If you forget step 3, the next sibling starts from a corrupted state, and the bug is usually silent: you simply get wrong or missing answers. Sharing one list and undoing is much cheaper than copying the list at every call: per edge instead of .

Three questions for every backtracking problem

Before writing code, answer these on paper:

  1. What is one decision? (include element i or not; which number goes in position k; which column holds the queen in row r; where the next cut goes).
  2. When is a partial solution complete, and when is it a solution? (path length is k; all rows have queens; the remaining sum is 0).
  3. When is a partial solution hopeless? (two queens attack; the remaining sum is negative; a Sudoku cell has no legal digit). This is your pruning test, and it decides whether the search finishes in milliseconds or in years.

The Backtracking Template

Backtracking follows a consistent pattern. Memorize this template:

function backtrack(candidate, state):
    if is_solution(candidate):
        record(candidate)
        return

    for choice in get_choices(state):
        if is_valid(choice, state):
            make_choice(choice, state)        # choose
            backtrack(candidate, state)         # explore
            undo_choice(choice, state)          # unchoose (backtrack)
graph TD
    A["Start"] --> B["Make Choice 1"]
    A --> C["Make Choice 2"]
    A --> D["Make Choice 3"]
    B --> E["Choice 1.1"]
    B --> F["Choice 1.2 ✗<br/><small>pruned</small>"]
    C --> G["Choice 2.1 ✓<br/><small>solution!</small>"]
    C --> H["Choice 2.2"]
    D --> I["Choice 3.1 ✗<br/><small>pruned</small>"]
    style F fill:#f44336,color:#fff
    style G fill:#4CAF50,color:#fff
    style I fill:#f44336,color:#fff

The key insight: backtracking explores a decision tree. Each node represents a partial solution. Pruning cuts off entire subtrees that cannot lead to valid solutions.

The recursion tree for subsets of [1, 2, 3]

Here is the real tree that the Subsets code below walks. Each node is the current path. The edge label is the choose step; returning along the same edge is the matching unchoose. Every node is recorded as a subset, so there are exactly 8 nodes for subsets.

graph TD
    R["{} start=0"] -->|"choose 1"| A["{1} start=1"]
    R -->|"choose 2"| B["{2} start=2"]
    R -->|"choose 3"| C["{3} start=3"]
    A -->|"choose 2"| AB["{1,2} start=2"]
    A -->|"choose 3"| AC["{1,3} start=3"]
    AB -->|"choose 3"| ABC["{1,2,3} start=3"]
    B -->|"choose 3"| BC["{2,3} start=3"]

Notice the shape: a node at index start may only choose elements at positions start or later. That is what stops {2,1} from appearing as well as {1,2}: each subset is generated once, in increasing index order.

Trace table: subsets of [1, 2, 3]

Every event the program performs, in order. "Record" happens on entering a call. Recomputed by script; it matches the order in "Try It Yourself" below.

StepEventpath after the eventRecorded so far
1enter bt(0), record[][]
2choose 1[1]
3enter bt(1), record[1][], [1]
4choose 2[1,2]
5enter bt(2), record[1,2]+ [1,2]
6choose 3[1,2,3]
7enter bt(3), record; loop is empty, return[1,2,3]+ [1,2,3]
8unchoose 3[1,2]
9unchoose 2[1]
10choose 3[1,3]
11enter bt(3), record[1,3]+ [1,3]
12unchoose 3[1]
13unchoose 1[]
14choose 2[2]
15enter bt(2), record[2]+ [2]
16choose 3[2,3]
17enter bt(3), record[2,3]+ [2,3]
18unchoose 3[2]
19unchoose 2[]
20choose 3[3]
21enter bt(3), record[3]+ [3] (8 total)
22unchoose 3[]

Count the events: 8 records (one per node), 7 chooses and 7 unchooses (one per edge, since a tree with 8 nodes has 7 edges). Every choose has a matching unchoose, and path is empty again at the end. That balance is the invariant that makes backtracking correct.

Trace table: permutations of [1, 2, 3]

The permutation template uses a used[] array instead of a start index: at every level, any unused element may come next. The first 12 events cover the whole subtree under "1 first":

StepEventpathused (for 1, 2, 3)
1choose 1[1]T F F
2choose 2[1,2]T T F
3choose 3[1,2,3]T T T
4full length: record [1,2,3][1,2,3]T T T
5unchoose 3[1,2]T T F
6unchoose 2[1]T F F
7choose 3[1,3]T F T
8choose 2[1,3,2]T T T
9record [1,3,2][1,3,2]T T T
10unchoose 2[1,3]T F T
11unchoose 3[1]T F F
12unchoose 1[]F F F

The same pattern repeats for "2 first" (steps 13–24) and "3 first" (steps 25–36). In total the program makes 16 calls: 1 root + 3 + 6 + 6 leaves. In general the permutation tree has nodes, which is for (16 for ).

The three templates at a glance

Almost every enumeration problem is one of three shapes. They differ only in which choices are allowed at the next level:

TemplateNext choicesSolution when# solutionsRecursion-tree nodes
Subsetsindices start..n-1 (later ones only)every node
Combinations ( of )indices start..n-1, with room left for the restlen(path) == kat most
Permutationsany index not yet usedlen(path) == n
  • "Order does not matter" (a set of things) → pass start = i + 1 so indices only increase. Pass start = i if an element may be reused (combination sum).
  • "Order matters" (an arrangement) → loop over all indices and skip used ones.

The sections below give each template in detail; all of them in four languages follow after the duplicates section.

Permutations

Generate all permutations of a set of distinct elements.

TypeScript:

function permutations(nums: number[]): number[][] {
  const result: number[][] = [];

  function backtrack(path: number[], remaining: Set<number>): void {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (const num of remaining) {
      path.push(num);
      remaining.delete(num);

      backtrack(path, remaining);

      path.pop();            // undo choice
      remaining.add(num);    // restore
    }
  }

  backtrack([], new Set(nums));
  return result;
}

Python:

def permutations(nums: list[int]) -> list[list[int]]:
    result = []

    def backtrack(path: list[int], remaining: set[int]) -> None:
        if len(path) == len(nums):
            result.append(path[:])
            return

        for num in list(remaining):  # copy since we mutate
            path.append(num)
            remaining.remove(num)

            backtrack(path, remaining)

            path.pop()
            remaining.add(num)

    backtrack([], set(nums))
    return result

Complexity: — there are permutations and each takes to copy.

Permutations with Duplicates

Sort the input and skip duplicate choices at the same level of the decision tree.

Python:

def permutations_unique(nums: list[int]) -> list[list[int]]:
    result = []
    nums.sort()
    used = [False] * len(nums)

    def backtrack(path: list[int]) -> None:
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):
            if used[i]:
                continue
            # Skip duplicates: only use the first unused occurrence
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue

            used[i] = True
            path.append(nums[i])

            backtrack(path)

            path.pop()
            used[i] = False

    backtrack([])
    return result

Combinations

Choose elements from elements (order doesn't matter).

TypeScript:

function combinations(n: number, k: number): number[][] {
  const result: number[][] = [];

  function backtrack(start: number, path: number[]): void {
    if (path.length === k) {
      result.push([...path]);
      return;
    }

    // Pruning: need (k - path.length) more elements,
    // so don't start too late
    for (let i = start; i <= n - (k - path.length) + 1; i++) {
      path.push(i);
      backtrack(i + 1, path); // i + 1 prevents reuse
      path.pop();
    }
  }

  backtrack(1, []);
  return result;
}

Python:

def combinations(n: int, k: int) -> list[list[int]]:
    result = []

    def backtrack(start: int, path: list[int]) -> None:
        if len(path) == k:
            result.append(path[:])
            return

        # Pruning: need k - len(path) more elements
        for i in range(start, n - (k - len(path)) + 2):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result

Complexity: — there are combinations, each taking to copy.

Combination Sum

Find all combinations that sum to a target, with elements reusable.

Python:

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    result = []
    candidates.sort()

    def backtrack(start: int, path: list[int], remaining: int) -> None:
        if remaining == 0:
            result.append(path[:])
            return

        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # pruning: sorted, so all subsequent are too large

            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])  # i, not i+1 (reuse allowed)
            path.pop()

    backtrack(0, [], target)
    return result

Subsets

Generate all subsets (power set). Each element is either included or excluded.

TypeScript:

function subsets(nums: number[]): number[][] {
  const result: number[][] = [];

  function backtrack(index: number, path: number[]): void {
    result.push([...path]); // every path is a valid subset

    for (let i = index; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }

  backtrack(0, []);
  return result;
}

Python:

def subsets(nums: list[int]) -> list[list[int]]:
    result = []

    def backtrack(index: int, path: list[int]) -> None:
        result.append(path[:])

        for i in range(index, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

Complexity: — there are subsets, each taking to copy.

Duplicates: sort, then skip equal siblings

If the input contains repeated values, the plain templates produce repeated answers. Subsets of [1, 2, 2] would list [2] twice and [1, 2] twice, because "the first 2" and "the second 2" are different indices with the same value.

The fix has two parts:

  1. Sort the input so equal values sit next to each other.
  2. In each loop, skip a value equal to the one you just tried at this same level. For subsets and combinations the test is i > start and nums[i] == nums[i - 1].

Why i > start and not i > 0? The rule is about siblings: two children of the same node that would start with the same value produce identical subtrees. Going deeper with an equal value is fine and necessary, or [2, 2] would never appear. At i == start you are the first child at this level, so there is nothing to compare with.

graph TD
    R["{} start=0"] -->|"1"| A["{1}"]
    R -->|"2 (index 1)"| B["{2}"]
    R -.->|"2 (index 2) skipped"| X["duplicate subtree"]
    A -->|"2 (index 1)"| AB["{1,2}"]
    A -.->|"2 (index 2) skipped"| Y["duplicate subtree"]
    AB -->|"2 (index 2) deeper: allowed"| ABB["{1,2,2}"]
    B -->|"2 (index 2) deeper: allowed"| BB["{2,2}"]
    style X fill:#f44336,color:#fff
    style Y fill:#f44336,color:#fff

Result: [], [1], [1,2], [1,2,2], [2], [2,2], which is 6 subsets, not 8.

For permutations the rule shown above is i > 0 and nums[i] == nums[i-1] and not used[i-1]. Read it as "equal values must be used left to right": you may only place the second 1 if the first 1 is already in the path. Each distinct arrangement then corresponds to exactly one order of using the indices. [1, 1, 2] gives 3 permutations instead of ; [1, 1, 2, 2] gives .

Sort is not optional

The skip rule compares neighbours. Without sorting, the duplicates of [2, 1, 2] are not neighbours and the rule silently fails. In TypeScript, [10, 9, 1].sort() sorts as strings and gives [1, 10, 9]; always pass (a, b) => a - b.

Combination Sum II (each element at most once, input with duplicates) combines both ideas: sort, recurse with i + 1, skip equal siblings with i > start, and break once a value exceeds the remaining target.

All templates in four languages

Subsets, subsets with duplicates, combinations, combination sum, permutations and unique permutations. Each program asserts the outputs shown in this lesson.

def subsets(nums: list[int]) -> list[list[int]]:
    """Every node of the recursion tree is a subset: record on entry."""
    res: list[list[int]] = []
    path: list[int] = []

    def bt(start: int) -> None:
        res.append(path[:])                  # copy! path keeps changing
        for i in range(start, len(nums)):
            path.append(nums[i])             # choose
            bt(i + 1)                        # explore (only later indices)
            path.pop()                       # unchoose

    bt(0)
    return res

def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    nums = sorted(nums)                      # equal values become neighbours
    res: list[list[int]] = []
    path: list[int] = []

    def bt(start: int) -> None:
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue                     # same value already tried at this depth
            path.append(nums[i])
            bt(i + 1)
            path.pop()

    bt(0)
    return res

def combine(n: int, k: int) -> list[list[int]]:
    res: list[list[int]] = []
    path: list[int] = []

    def bt(start: int) -> None:
        if len(path) == k:
            res.append(path[:])
            return
        need = k - len(path)
        for i in range(start, n - need + 2):  # feasibility: leave room for the rest
            path.append(i)
            bt(i + 1)
            path.pop()

    bt(1)
    return res

def combination_sum(cands: list[int], target: int) -> list[list[int]]:
    cands = sorted(cands)
    res: list[list[int]] = []
    path: list[int] = []

    def bt(start: int, remaining: int) -> None:
        if remaining == 0:
            res.append(path[:])
            return
        for i in range(start, len(cands)):
            if cands[i] > remaining:
                break                        # sorted: every later value is too big too
            path.append(cands[i])
            bt(i, remaining - cands[i])      # i, not i + 1: reuse allowed
            path.pop()

    bt(0, target)
    return res

def permute(nums: list[int]) -> list[list[int]]:
    res: list[list[int]] = []
    path: list[int] = []
    used = [False] * len(nums)

    def bt() -> None:
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            bt()
            path.pop()
            used[i] = False

    bt()
    return res

def permute_unique(nums: list[int]) -> list[list[int]]:
    nums = sorted(nums)
    res: list[list[int]] = []
    path: list[int] = []
    used = [False] * len(nums)

    def bt() -> None:
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue                     # use equal values left to right only
            used[i] = True
            path.append(nums[i])
            bt()
            path.pop()
            used[i] = False

    bt()
    return res

if __name__ == "__main__":
    assert subsets([1, 2, 3]) == [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
    assert subsets_with_dup([2, 1, 2]) == [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
    assert combine(4, 2) == [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
    assert combination_sum([2, 3, 6, 7], 7) == [[2, 2, 3], [7]]
    assert permute([1, 2, 3]) == [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    assert permute_unique([1, 1, 2]) == [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
    assert len(subsets(list(range(10)))) == 1024
    assert len(permute_unique([1, 1, 2, 2])) == 6
    print("subsets:", subsets([1, 2, 3]))
    print("permute_unique([1,1,2]):", permute_unique([1, 1, 2]))
    print("all template checks passed")
import java.util.*;

public class Templates {
    static void subsets(int[] nums, int start, Deque<Integer> path, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));            // copy: path keeps changing
        for (int i = start; i < nums.length; i++) {
            path.addLast(nums[i]);                 // choose
            subsets(nums, i + 1, path, res);       // explore
            path.removeLast();                     // unchoose
        }
    }

    static void subsetsWithDup(int[] nums, int start, Deque<Integer> path, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue; // skip equal sibling
            path.addLast(nums[i]);
            subsetsWithDup(nums, i + 1, path, res);
            path.removeLast();
        }
    }

    static void combine(int n, int k, int start, Deque<Integer> path, List<List<Integer>> res) {
        if (path.size() == k) { res.add(new ArrayList<>(path)); return; }
        int need = k - path.size();
        for (int i = start; i <= n - need + 1; i++) {   // leave room for the rest
            path.addLast(i);
            combine(n, k, i + 1, path, res);
            path.removeLast();
        }
    }

    static void combinationSum(int[] c, int start, int remaining, Deque<Integer> path, List<List<Integer>> res) {
        if (remaining == 0) { res.add(new ArrayList<>(path)); return; }
        for (int i = start; i < c.length; i++) {
            if (c[i] > remaining) break;               // sorted: the rest are bigger
            path.addLast(c[i]);
            combinationSum(c, i, remaining - c[i], path, res); // i: reuse allowed
            path.removeLast();
        }
    }

    static void permute(int[] nums, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true; path.addLast(nums[i]);
            permute(nums, used, path, res);
            path.removeLast(); used[i] = false;
        }
    }

    static void permuteUnique(int[] nums, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // left-to-right only
            used[i] = true; path.addLast(nums[i]);
            permuteUnique(nums, used, path, res);
            path.removeLast(); used[i] = false;
        }
    }

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    public static void main(String[] args) {
        List<List<Integer>> r = new ArrayList<>();
        subsets(new int[]{1, 2, 3}, 0, new ArrayDeque<>(), r);
        check(r.toString().equals("[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]"), "subsets");

        int[] d = {2, 1, 2}; Arrays.sort(d);
        r = new ArrayList<>(); subsetsWithDup(d, 0, new ArrayDeque<>(), r);
        check(r.toString().equals("[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]"), "subsetsWithDup");

        r = new ArrayList<>(); combine(4, 2, 1, new ArrayDeque<>(), r);
        check(r.toString().equals("[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]"), "combine");

        int[] c = {2, 3, 6, 7}; Arrays.sort(c);
        r = new ArrayList<>(); combinationSum(c, 0, 7, new ArrayDeque<>(), r);
        check(r.toString().equals("[[2, 2, 3], [7]]"), "combinationSum");

        r = new ArrayList<>(); permute(new int[]{1, 2, 3}, new boolean[3], new ArrayDeque<>(), r);
        check(r.toString().equals("[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]"), "permute");

        r = new ArrayList<>(); permuteUnique(new int[]{1, 1, 2}, new boolean[3], new ArrayDeque<>(), r);
        check(r.toString().equals("[[1, 1, 2], [1, 2, 1], [2, 1, 1]]"), "permuteUnique");

        System.out.println("permuteUnique([1,1,2]): " + r);
        System.out.println("all template checks passed");
    }
}
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;
using VVI = vector<vector<int>>;

VVI subsets(const vector<int>& nums) {
    VVI res; vector<int> path;
    function<void(int)> bt = [&](int start) {
        res.push_back(path);                       // copy: path keeps changing
        for (int i = start; i < (int)nums.size(); i++) {
            path.push_back(nums[i]);               // choose
            bt(i + 1);                             // explore
            path.pop_back();                       // unchoose
        }
    };
    bt(0);
    return res;
}

VVI subsetsWithDup(vector<int> nums) {
    sort(nums.begin(), nums.end());
    VVI res; vector<int> path;
    function<void(int)> bt = [&](int start) {
        res.push_back(path);
        for (int i = start; i < (int)nums.size(); i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;  // skip equal sibling
            path.push_back(nums[i]);
            bt(i + 1);
            path.pop_back();
        }
    };
    bt(0);
    return res;
}

VVI combine(int n, int k) {
    VVI res; vector<int> path;
    function<void(int)> bt = [&](int start) {
        if ((int)path.size() == k) { res.push_back(path); return; }
        int need = k - (int)path.size();
        for (int i = start; i <= n - need + 1; i++) {          // leave room for the rest
            path.push_back(i);
            bt(i + 1);
            path.pop_back();
        }
    };
    bt(1);
    return res;
}

VVI combinationSum(vector<int> c, int target) {
    sort(c.begin(), c.end());
    VVI res; vector<int> path;
    function<void(int, int)> bt = [&](int start, int remaining) {
        if (remaining == 0) { res.push_back(path); return; }
        for (int i = start; i < (int)c.size(); i++) {
            if (c[i] > remaining) break;                       // sorted: the rest are bigger
            path.push_back(c[i]);
            bt(i, remaining - c[i]);                           // i: reuse allowed
            path.pop_back();
        }
    };
    bt(0, target);
    return res;
}

VVI permute(const vector<int>& nums) {
    VVI res; vector<int> path; vector<bool> used(nums.size(), false);
    function<void()> bt = [&]() {
        if (path.size() == nums.size()) { res.push_back(path); return; }
        for (size_t i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            used[i] = true; path.push_back(nums[i]);
            bt();
            path.pop_back(); used[i] = false;
        }
    };
    bt();
    return res;
}

VVI permuteUnique(vector<int> nums) {
    sort(nums.begin(), nums.end());
    VVI res; vector<int> path; vector<bool> used(nums.size(), false);
    function<void()> bt = [&]() {
        if (path.size() == nums.size()) { res.push_back(path); return; }
        for (size_t i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // left-to-right only
            used[i] = true; path.push_back(nums[i]);
            bt();
            path.pop_back(); used[i] = false;
        }
    };
    bt();
    return res;
}

int main() {
    assert((subsets({1, 2, 3}) == VVI{{}, {1}, {1, 2}, {1, 2, 3}, {1, 3}, {2}, {2, 3}, {3}}));
    assert((subsetsWithDup({2, 1, 2}) == VVI{{}, {1}, {1, 2}, {1, 2, 2}, {2}, {2, 2}}));
    assert((combine(4, 2) == VVI{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}));
    assert((combinationSum({2, 3, 6, 7}, 7) == VVI{{2, 2, 3}, {7}}));
    assert((permute({1, 2, 3}) == VVI{{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}}));
    assert((permuteUnique({1, 1, 2}) == VVI{{1, 1, 2}, {1, 2, 1}, {2, 1, 1}}));
    assert(subsets(vector<int>(10, 0)).size() == 1024);
    cout << "all template checks passed\n";
}
function subsets(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const bt = (start: number): void => {
    res.push([...path]); // copy: path keeps changing
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]); // choose
      bt(i + 1); // explore
      path.pop(); // unchoose
    }
  };
  bt(0);
  return res;
}

function subsetsWithDup(input: number[]): number[][] {
  const nums = [...input].sort((a, b) => a - b); // numeric sort, not the default string sort
  const res: number[][] = [];
  const path: number[] = [];
  const bt = (start: number): void => {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i] === nums[i - 1]) continue; // skip equal sibling
      path.push(nums[i]);
      bt(i + 1);
      path.pop();
    }
  };
  bt(0);
  return res;
}

function combine(n: number, k: number): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const bt = (start: number): void => {
    if (path.length === k) {
      res.push([...path]);
      return;
    }
    const need = k - path.length;
    for (let i = start; i <= n - need + 1; i++) { // leave room for the rest
      path.push(i);
      bt(i + 1);
      path.pop();
    }
  };
  bt(1);
  return res;
}

function combinationSum(input: number[], target: number): number[][] {
  const c = [...input].sort((a, b) => a - b);
  const res: number[][] = [];
  const path: number[] = [];
  const bt = (start: number, remaining: number): void => {
    if (remaining === 0) {
      res.push([...path]);
      return;
    }
    for (let i = start; i < c.length; i++) {
      if (c[i] > remaining) break; // sorted: the rest are bigger
      path.push(c[i]);
      bt(i, remaining - c[i]); // i: reuse allowed
      path.pop();
    }
  };
  bt(0, target);
  return res;
}

function permute(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const used: boolean[] = new Array(nums.length).fill(false);
  const bt = (): void => {
    if (path.length === nums.length) {
      res.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);
      bt();
      path.pop();
      used[i] = false;
    }
  };
  bt();
  return res;
}

function permuteUnique(input: number[]): number[][] {
  const nums = [...input].sort((a, b) => a - b);
  const res: number[][] = [];
  const path: number[] = [];
  const used: boolean[] = new Array(nums.length).fill(false);
  const bt = (): void => {
    if (path.length === nums.length) {
      res.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue; // left-to-right only
      used[i] = true;
      path.push(nums[i]);
      bt();
      path.pop();
      used[i] = false;
    }
  };
  bt();
  return res;
}

function check(ok: boolean, what: string): void {
  if (!ok) throw new Error("failed: " + what);
}
const same = (a: unknown, b: unknown): boolean => JSON.stringify(a) === JSON.stringify(b);

check(same(subsets([1, 2, 3]), [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]), "subsets");
check(same(subsetsWithDup([2, 1, 2]), [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]), "subsetsWithDup");
check(same(combine(4, 2), [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]), "combine");
check(same(combinationSum([2, 3, 6, 7], 7), [[2, 2, 3], [7]]), "combinationSum");
check(same(permute([1, 2, 3]), [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]), "permute");
check(same(permuteUnique([1, 1, 2]), [[1, 1, 2], [1, 2, 1], [2, 1, 1]]), "permuteUnique");
check(subsets([10, 2, 3, 4, 5, 6, 7, 8, 9, 1]).length === 1024, "2^10");
console.log("all template checks passed");

Pruning Strategies

Pruning is what makes backtracking practical. Without pruning, backtracking degenerates into brute-force enumeration.

Types of Pruning

StrategyTechniqueExample
Constraint propagationCheck constraints before recursingN-Queens: skip attacked positions
Bound pruningCompare current best with theoretical best of branchBranch and bound optimization
Symmetry breakingAvoid exploring symmetric configurationsFix first queen to top half in N-Queens
Value orderingTry most constrained choices firstSudoku: fill cell with fewest candidates first
Feasibility checkVerify partial solution can still lead to a complete oneCombination sum: stop if remaining < 0

Pruning Example: Combination Sum with Sorting

def combination_sum_pruned(candidates: list[int], target: int) -> list[list[int]]:
    result = []
    candidates.sort()  # sort to enable pruning

    def backtrack(start: int, path: list[int], remaining: int) -> None:
        if remaining == 0:
            result.append(path[:])
            return

        for i in range(start, len(candidates)):
            # PRUNING: since array is sorted, all remaining candidates
            # are >= candidates[i], so if this one exceeds the target,
            # we can skip all of them
            if candidates[i] > remaining:
                break

            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])
            path.pop()

    backtrack(0, [], target)
    return result

Most Constrained Variable (MCV)

For constraint satisfaction problems, choosing the most constrained variable first (the cell with fewest valid options in Sudoku, the most attacked row in N-Queens) dramatically reduces the search space.

The three kinds of pruning, with measured numbers

All the strategies in the table above fall into three families. Each one is a test that runs at a node and answers "can this subtree still matter?"

1. Feasibility pruning: "can this partial solution still become valid?" Cut when a rule is already broken (two queens attack) or can no longer be met (the remaining target is negative; fewer elements remain than you still need). The test must be a necessary condition: if it says "no", there must truly be no solution below. A test that is too strict silently loses answers.

Measured on Combination Sum (number of recursive calls, including calls that immediately fail):

InputNo sort, stop only when remaining < 0Sorted + break when a value exceeds remaining
[2,3,6,7], target 728 calls10 calls
[2,3,5], target 823 calls13 calls

The answers are identical ([[2,2,3],[7]] and [[2,2,2,2],[2,3,3],[3,5]]); only the wasted work differs. Sorting turns "this value is too big" into "this value and every value after it are too big", so one comparison cuts many siblings at once.

2. Bounding (branch and bound): "can this subtree beat the best answer found so far?" For optimisation problems, keep the best complete answer seen so far. At each node compute an optimistic bound: a value at least as good as anything in the subtree. If even the bound cannot beat the current best, cut. A tiny 0/1 knapsack (weights [5,4,6,3], values [10,40,30,50], capacity 10; best value 90) shows how much the bound's quality matters:

Bound usedNodes visited
none (feasibility only)23
current value + sum of all remaining values17
current value + fractional-knapsack bound (items sorted by value/weight)7

The fractional bound is tighter (closer to the truth), so it prunes more. The bound must never be pessimistic, or you may cut the subtree holding the real optimum. This is the same idea that makes integer-programming solvers practical; see Linear Programming.

3. Ordering: "which choice should I try first?" Ordering does not remove solutions, but it changes how early the search fails or succeeds.

  • Variable ordering: decide the most constrained variable first (MRV, "minimum remaining values", also called fail-first). A cell with one legal digit costs nothing to fill; a cell with zero legal digits proves the branch dead immediately. On the hard Sudoku in the Sudoku section, MRV cuts guesses from 49,558 to 10,101.
  • Value ordering: try the most promising value first (least constraining value, or the greedy choice). This helps when you need one solution or a good bound early; it does not help when you must enumerate all solutions, since every branch is visited anyway.
  • Symmetry breaking: if the problem has symmetry, explore only one representative. For N-Queens, placing the first queen only in the left half of the first row and doubling the count (plus the middle column when is odd) halves the work: 1,029 calls instead of 2,057 for .

Rule of thumb

Feasibility pruning is for all solutions, bounding is for the best solution, and ordering is for any solution (or a good bound fast). Most real solvers use all three.

N-Queens

Place queens on an chessboard such that no two queens attack each other (same row, column, or diagonal).

graph TD
    subgraph "4-Queens Solution"
        R0["_ Q _ _"]
        R1["_ _ _ Q"]
        R2["Q _ _ _"]
        R3["_ _ Q _"]
    end

TypeScript:

function solveNQueens(n: number): string[][] {
  const results: string[][] = [];
  const cols = new Set<number>();
  const diag1 = new Set<number>(); // row - col
  const diag2 = new Set<number>(); // row + col
  const board: string[][] = Array.from({ length: n }, () =>
    new Array(n).fill('.')
  );

  function backtrack(row: number): void {
    if (row === n) {
      results.push(board.map(r => r.join('')));
      return;
    }

    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) {
        continue; // pruning: position is under attack
      }

      // Place queen
      board[row][col] = 'Q';
      cols.add(col);
      diag1.add(row - col);
      diag2.add(row + col);

      backtrack(row + 1);

      // Remove queen (backtrack)
      board[row][col] = '.';
      cols.delete(col);
      diag1.delete(row - col);
      diag2.delete(row + col);
    }
  }

  backtrack(0);
  return results;
}

Python:

def solve_n_queens(n: int) -> list[list[str]]:
    results = []
    cols = set()
    diag1 = set()  # row - col
    diag2 = set()  # row + col
    board = [['.' ] * n for _ in range(n)]

    def backtrack(row: int) -> None:
        if row == n:
            results.append([''.join(r) for r in board])
            return

        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue

            board[row][col] = 'Q'
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)

            backtrack(row + 1)

            board[row][col] = '.'
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0)
    return results

Key insight: The diagonal constraint is elegant — cells on the same diagonal share the same row - col value (one diagonal direction) or row + col value (the other direction). Using sets for columns and both diagonals gives conflict checking.

N-Queens with bitmasks

The set-based version above does three hash lookups per column per row. A faster and very compact version stores the attacked columns of the current row in three integers, one bit per column (see Bit Manipulation for the operators):

  • cols: bit c is set if some queen is already in column c.
  • diag: bit c is set if a queen attacks column c along a "\" diagonal in this row.
  • anti: bit c is set if a queen attacks column c along a "/" diagonal in this row.

The trick is how the diagonal masks move between rows. A queen at column c attacks column c + 1 one row down along "\", and column c − 1 along "/". So when you go down a row, shift diag left by one and anti right by one. Bits shifted off the board are masked away with full = (1 << n) - 1.

graph LR
    A["row r: queen at column 2<br/>cols=00100 diag=00100 anti=00100"] -->|"go down one row"| B["row r+1 attacked:<br/>cols=00100 diag=01000 anti=00010"]
    B -->|"free = full AND NOT (cols OR diag OR anti)"| C["free = 10001<br/>columns 0 and 4 are safe"]

(Bit strings are written with column 4 on the left and column 0 on the right; diag and anti here show only this queen's attacks.)

Two more bit tricks finish it:

  • free & -free isolates the lowest set bit: the next safe column to try. In two's complement, -x flips every bit above the lowest 1, so the AND keeps only that bit.
  • free ^= bit removes that column from the to-do set.

Notice there is no explicit "unchoose" step. The new masks are passed by value as arguments, so the caller's masks are untouched when the call returns. Passing immutable state by value is the other way to backtrack: undo is automatic, at the price of building a new state per call. For three integers that price is zero.

Counts and the size of the search, recomputed by script:

SolutionsRecursive calls (bitmask search) (one queen per row, no checks) (one per row and column)
11211
20342
306276
421725624
510543,125120
6415346,656720
740552823,5435,040
8922,05716,777,21640,320
93528,394387,420,489362,880
1072435,53910,000,000,0003,628,800

The solution counts match OEIS A000170. The set-based version visits exactly the same 2,057 nodes for (it applies the same test); the bitmask version is just cheaper per node. In one CPython 3 run on a laptop, took about 0.56 s with sets and 0.17 s with bitmasks, both visiting 856,189 nodes. Treat such timings as rough: they vary by machine.

def total_n_queens(n: int) -> int:
    """Count N-Queens solutions with three bitmasks (bit i = column i is attacked)."""
    full = (1 << n) - 1

    def place(cols: int, diag: int, anti: int) -> int:
        if cols == full:                       # one queen in every column => n queens placed
            return 1
        count = 0
        free = full & ~(cols | diag | anti)    # columns safe in this row
        while free:
            bit = free & -free                 # lowest free column
            free ^= bit                        # remove it from the to-do set
            count += place(cols | bit,
                           ((diag | bit) << 1) & full,  # "\" attacks shift one column right
                           (anti | bit) >> 1)           # "/" attacks shift one column left
        return count

    return place(0, 0, 0)

if __name__ == "__main__":
    expected = [1, 0, 0, 2, 10, 4, 40, 92, 352, 724]
    got = [total_n_queens(n) for n in range(1, 11)]
    print("n = 1..10:", got)
    assert got == expected
public class NQueens {
    static int full;

    // bit i set = column i is attacked in the current row
    static int place(int cols, int diag, int anti) {
        if (cols == full) return 1;                 // every column has a queen
        int count = 0;
        int free = full & ~(cols | diag | anti);    // safe columns in this row
        while (free != 0) {
            int bit = free & -free;                 // lowest safe column
            free ^= bit;
            count += place(cols | bit, ((diag | bit) << 1) & full, (anti | bit) >> 1);
        }
        return count;
    }

    static int totalNQueens(int n) {
        full = (1 << n) - 1;
        return place(0, 0, 0);
    }

    public static void main(String[] args) {
        int[] expected = {1, 0, 0, 2, 10, 4, 40, 92, 352, 724};
        StringBuilder sb = new StringBuilder("n = 1..10:");
        for (int n = 1; n <= 10; n++) {
            int got = totalNQueens(n);
            if (got != expected[n - 1]) throw new AssertionError("n=" + n + " got " + got);
            sb.append(' ').append(got);
        }
        System.out.println(sb);
    }
}
#include <cassert>
#include <cstdio>

// bit i set = column i is attacked in the current row
static int place(int full, int cols, int diag, int anti) {
    if (cols == full) return 1;                     // every column has a queen
    int count = 0;
    int free = full & ~(cols | diag | anti);        // safe columns in this row
    while (free) {
        int bit = free & -free;                     // lowest safe column
        free ^= bit;
        count += place(full, cols | bit, ((diag | bit) << 1) & full, (anti | bit) >> 1);
    }
    return count;
}

int totalNQueens(int n) { return place((1 << n) - 1, 0, 0, 0); }

int main() {
    const int expected[] = {1, 0, 0, 2, 10, 4, 40, 92, 352, 724};
    std::printf("n = 1..10:");
    for (int n = 1; n <= 10; n++) {
        int got = totalNQueens(n);
        assert(got == expected[n - 1]);
        std::printf(" %d", got);
    }
    std::printf("\n");
}
function totalNQueens(n: number): number {
  const full = (1 << n) - 1; // fine up to n = 30 with 32-bit bitwise ops
  // bit i set = column i is attacked in the current row
  const place = (cols: number, diag: number, anti: number): number => {
    if (cols === full) return 1; // every column has a queen
    let count = 0;
    let free = full & ~(cols | diag | anti); // safe columns in this row
    while (free !== 0) {
      const bit = free & -free; // lowest safe column
      free ^= bit;
      count += place(cols | bit, ((diag | bit) << 1) & full, (anti | bit) >>> 1);
    }
    return count;
  };
  return place(0, 0, 0);
}

const expected = [1, 0, 0, 2, 10, 4, 40, 92, 352, 724];
const got: number[] = [];
for (let n = 1; n <= 10; n++) got.push(totalNQueens(n));
console.log("n = 1..10:", got.join(" "));
if (got.join() !== expected.join()) throw new Error("mismatch");

Sudoku Solver

Fill a 9x9 grid so each row, column, and 3x3 box contains digits 1-9 exactly once.

Python:

def solve_sudoku(board: list[list[str]]) -> bool:
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    # Initialize constraints from existing numbers
    for r in range(9):
        for c in range(9):
            if board[r][c] != '.':
                num = board[r][c]
                rows[r].add(num)
                cols[c].add(num)
                boxes[(r // 3) * 3 + c // 3].add(num)

    def backtrack(r: int, c: int) -> bool:
        if r == 9:
            return True  # all cells filled
        next_r, next_c = (r, c + 1) if c < 8 else (r + 1, 0)

        if board[r][c] != '.':
            return backtrack(next_r, next_c)

        box_idx = (r // 3) * 3 + c // 3
        for num in '123456789':
            if num in rows[r] or num in cols[c] or num in boxes[box_idx]:
                continue

            board[r][c] = num
            rows[r].add(num)
            cols[c].add(num)
            boxes[box_idx].add(num)

            if backtrack(next_r, next_c):
                return True

            board[r][c] = '.'
            rows[r].remove(num)
            cols[c].remove(num)
            boxes[box_idx].remove(num)

        return False  # no valid number for this cell

    backtrack(0, 0)
    return True

TypeScript:

function solveSudoku(board: string[][]): void {
  const rows: Set<string>[] = Array.from({ length: 9 }, () => new Set());
  const cols: Set<string>[] = Array.from({ length: 9 }, () => new Set());
  const boxes: Set<string>[] = Array.from({ length: 9 }, () => new Set());

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (board[r][c] !== '.') {
        const num = board[r][c];
        rows[r].add(num);
        cols[c].add(num);
        boxes[Math.floor(r / 3) * 3 + Math.floor(c / 3)].add(num);
      }
    }
  }

  function backtrack(r: number, c: number): boolean {
    if (r === 9) return true;
    const [nr, nc] = c < 8 ? [r, c + 1] : [r + 1, 0];

    if (board[r][c] !== '.') return backtrack(nr, nc);

    const boxIdx = Math.floor(r / 3) * 3 + Math.floor(c / 3);

    for (let num = 1; num <= 9; num++) {
      const s = String(num);
      if (rows[r].has(s) || cols[c].has(s) || boxes[boxIdx].has(s)) continue;

      board[r][c] = s;
      rows[r].add(s);
      cols[c].add(s);
      boxes[boxIdx].add(s);

      if (backtrack(nr, nc)) return true;

      board[r][c] = '.';
      rows[r].delete(s);
      cols[c].delete(s);
      boxes[boxIdx].delete(s);
    }

    return false;
  }

  backtrack(0, 0);
}

Correction

The Python solve_sudoku above ends with backtrack(0, 0) followed by return True, so it reports success even for an unsolvable puzzle. Return the search result instead: return backtrack(0, 0). (LeetCode's version guarantees a solution, which is why the bug is easy to miss.)

Constraint propagation and MRV

The solver above fills cells in reading order (row 0 left to right, then row 1, …) and tries digits 1 to 9. That is fine for newspaper puzzles and slow for hard ones. Two ideas from constraint programming fix most of that.

A constraint satisfaction problem (CSP) has variables (the 81 cells), domains (the digits each cell may still take) and constraints (no repeat in a row, column or box). Two terms you will meet everywhere:

  • Constraint propagation: after each assignment, remove the now-illegal values from the domains of related cells (its peers: the 20 other cells in its row, column and box). Repeat while it keeps forcing things. The two classic Sudoku rules are
    • naked single: a cell's domain has shrunk to one digit, so that digit must go there;
    • hidden single: a digit fits in only one cell of some row, column or box, so it must go there. If any domain becomes empty, the current branch is dead.
  • MRV (minimum remaining values): when you must guess, guess at the cell with the smallest domain. A 2-candidate cell has a 50% chance of guessing right; a 9-candidate cell, 11%.

The simplest form of propagation is forward checking: compute each empty cell's candidates from the row, column and box masks, and fail the branch at once if any cell has zero. The four-language solver below does exactly this plus MRV, with each domain stored as a 9-bit mask (bit d − 1 set means digit d is still allowed).

Measured on two puzzles (the LeetCode example with 51 blanks, and a 60-blank puzzle widely circulated in 2012 as "the world's hardest Sudoku", attributed to Arto Inkala). "Guesses" counts digit placements made by the search:

SolverLeetCode example"Hardest" puzzle
Reading order, digits 1–9 (the code above)4,20849,558
MRV + forward checking, bitmasks (code below)51 (no wrong guess at all)10,101
MRV + full propagation (naked and hidden singles)0 (solved by propagation alone)172

On the hard puzzle, full propagation cuts guesses by a factor of about 288. Note the cost per node rises too: MRV scans all 81 cells at every node. In one CPython run, the MRV version actually took longer in wall-clock time than the reading-order version on the hard puzzle (about 0.17 s against 0.07 s) despite 5 times fewer guesses. Fewer nodes is not automatically faster; measure. Peter Norvig's essay "Solving Every Sudoku Puzzle" is the classic write-up of the propagation + MRV design.

class Sudoku:
    """Bitmask Sudoku solver: MRV (fewest candidates first) + forward checking."""

    def __init__(self, rows: list[str]) -> None:
        self.g = [[0 if ch == "." else int(ch) for ch in r] for r in rows]
        self.row = [0] * 9                    # bit d-1 set = digit d used in that row
        self.col = [0] * 9
        self.box = [0] * 9
        self.guesses = 0
        for r in range(9):
            for c in range(9):
                if self.g[r][c]:
                    self._flip(r, c, 1 << (self.g[r][c] - 1))

    def _flip(self, r: int, c: int, bit: int) -> None:
        self.row[r] ^= bit                    # XOR both places and removes a digit
        self.col[c] ^= bit
        self.box[r // 3 * 3 + c // 3] ^= bit

    def solve(self) -> bool:
        best, best_count, best_cand = None, 10, 0
        for r in range(9):                    # MRV: find the most constrained empty cell
            for c in range(9):
                if self.g[r][c] == 0:
                    cand = ~(self.row[r] | self.col[c] | self.box[r // 3 * 3 + c // 3]) & 0x1FF
                    k = bin(cand).count("1")
                    if k < best_count:
                        best, best_count, best_cand = (r, c), k, cand
        if best is None:
            return True                       # no empty cell left: solved
        if best_count == 0:
            return False                      # forward check: a cell has no legal digit
        r, c = best
        while best_cand:
            bit = best_cand & -best_cand
            best_cand ^= bit
            self.guesses += 1
            self.g[r][c] = bit.bit_length()   # choose
            self._flip(r, c, bit)
            if self.solve():                  # explore
                return True
            self._flip(r, c, bit)             # unchoose
            self.g[r][c] = 0
        return False

if __name__ == "__main__":
    puzzle = ["8........", "..36.....", ".7..9.2..", ".5...7...", "....457..",
              "...1...3.", "..1....68", "..85...1.", ".9....4.."]
    s = Sudoku(puzzle)
    assert s.solve()
    solved = ["".join(map(str, r)) for r in s.g]
    assert solved[0] == "812753649" and solved[8] == "796318452"
    for r in range(9):                        # every row, column and box holds 1..9
        assert sorted(solved[r]) == list("123456789")
        assert sorted(solved[i][r] for i in range(9)) == list("123456789")
        assert sorted(solved[r // 3 * 3 + i // 3][r % 3 * 3 + i % 3] for i in range(9)) == list("123456789")
    print("\n".join(solved))
    print("guesses:", s.guesses)
public class Sudoku {
    final int[][] g = new int[9][9];
    final int[] row = new int[9], col = new int[9], box = new int[9]; // bit d-1 = digit d used
    long guesses = 0;

    Sudoku(String[] rows) {
        for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++) {
                char ch = rows[r].charAt(c);
                if (ch != '.') { g[r][c] = ch - '0'; flip(r, c, 1 << (g[r][c] - 1)); }
            }
    }

    void flip(int r, int c, int bit) {              // XOR both places and removes a digit
        row[r] ^= bit; col[c] ^= bit; box[r / 3 * 3 + c / 3] ^= bit;
    }

    boolean solve() {
        int br = -1, bc = -1, bestCount = 10, bestCand = 0;
        for (int r = 0; r < 9; r++)                 // MRV: most constrained empty cell
            for (int c = 0; c < 9; c++)
                if (g[r][c] == 0) {
                    int cand = ~(row[r] | col[c] | box[r / 3 * 3 + c / 3]) & 0x1FF;
                    int k = Integer.bitCount(cand);
                    if (k < bestCount) { br = r; bc = c; bestCount = k; bestCand = cand; }
                }
        if (br < 0) return true;                    // solved
        if (bestCount == 0) return false;           // forward check failed
        while (bestCand != 0) {
            int bit = bestCand & -bestCand;
            bestCand ^= bit;
            guesses++;
            g[br][bc] = Integer.numberOfTrailingZeros(bit) + 1;  // choose
            flip(br, bc, bit);
            if (solve()) return true;                            // explore
            flip(br, bc, bit);                                   // unchoose
            g[br][bc] = 0;
        }
        return false;
    }

    public static void main(String[] args) {
        String[] puzzle = {"8........", "..36.....", ".7..9.2..", ".5...7...", "....457..",
                           "...1...3.", "..1....68", "..85...1.", ".9....4.."};
        Sudoku s = new Sudoku(puzzle);
        if (!s.solve()) throw new AssertionError("no solution");
        StringBuilder sb = new StringBuilder();
        for (int[] r : s.g) { for (int v : r) sb.append(v); sb.append('\n'); }
        String out = sb.toString();
        if (!out.startsWith("812753649") || !out.endsWith("796318452\n")) throw new AssertionError(out);
        System.out.print(out);
        System.out.println("guesses: " + s.guesses);
    }
}
#include <array>
#include <bitset>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

struct Sudoku {
    std::array<std::array<int, 9>, 9> g{};
    std::array<int, 9> row{}, col{}, box{};   // bit d-1 set = digit d used
    long guesses = 0;

    explicit Sudoku(const std::vector<std::string>& rows) {
        for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++)
                if (rows[r][c] != '.') { g[r][c] = rows[r][c] - '0'; flip(r, c, 1 << (g[r][c] - 1)); }
    }

    void flip(int r, int c, int bit) {         // XOR both places and removes a digit
        row[r] ^= bit; col[c] ^= bit; box[r / 3 * 3 + c / 3] ^= bit;
    }

    bool solve() {
        int br = -1, bc = -1, bestCount = 10, bestCand = 0;
        for (int r = 0; r < 9; r++)            // MRV: most constrained empty cell
            for (int c = 0; c < 9; c++)
                if (g[r][c] == 0) {
                    int cand = ~(row[r] | col[c] | box[r / 3 * 3 + c / 3]) & 0x1FF;
                    int k = (int)std::bitset<9>(cand).count();
                    if (k < bestCount) { br = r; bc = c; bestCount = k; bestCand = cand; }
                }
        if (br < 0) return true;               // solved
        if (bestCount == 0) return false;      // forward check failed
        while (bestCand) {
            int bit = bestCand & -bestCand;
            bestCand ^= bit;
            guesses++;
            g[br][bc] = __builtin_ctz(bit) + 1;   // choose
            flip(br, bc, bit);
            if (solve()) return true;             // explore
            flip(br, bc, bit);                    // unchoose
            g[br][bc] = 0;
        }
        return false;
    }
};

int main() {
    Sudoku s({"8........", "..36.....", ".7..9.2..", ".5...7...", "....457..",
              "...1...3.", "..1....68", "..85...1.", ".9....4.."});
    bool ok = s.solve();
    assert(ok);
    std::string first, last;
    for (int c = 0; c < 9; c++) { first += char('0' + s.g[0][c]); last += char('0' + s.g[8][c]); }
    assert(first == "812753649" && last == "796318452");
    for (auto& r : s.g) { for (int v : r) std::cout << v; std::cout << '\n'; }
    std::cout << "guesses: " << s.guesses << '\n';
}
const popcount = (x: number): number => {
  let k = 0;
  for (; x !== 0; x &= x - 1) k++;
  return k;
};

class Sudoku {
  g: number[][];
  row = new Array<number>(9).fill(0); // bit d-1 set = digit d used
  col = new Array<number>(9).fill(0);
  box = new Array<number>(9).fill(0);
  guesses = 0;

  constructor(rows: string[]) {
    this.g = rows.map((r) => [...r].map((ch) => (ch === "." ? 0 : Number(ch))));
    for (let r = 0; r < 9; r++)
      for (let c = 0; c < 9; c++)
        if (this.g[r][c] !== 0) this.flip(r, c, 1 << (this.g[r][c] - 1));
  }

  flip(r: number, c: number, bit: number): void {
    // XOR both places and removes a digit
    this.row[r] ^= bit;
    this.col[c] ^= bit;
    this.box[Math.floor(r / 3) * 3 + Math.floor(c / 3)] ^= bit;
  }

  solve(): boolean {
    let br = -1, bc = -1, bestCount = 10, bestCand = 0;
    for (let r = 0; r < 9; r++) // MRV: most constrained empty cell
      for (let c = 0; c < 9; c++)
        if (this.g[r][c] === 0) {
          const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
          const cand = ~(this.row[r] | this.col[c] | this.box[b]) & 0x1ff;
          const k = popcount(cand);
          if (k < bestCount) {
            br = r; bc = c; bestCount = k; bestCand = cand;
          }
        }
    if (br < 0) return true; // solved
    if (bestCount === 0) return false; // forward check failed
    while (bestCand !== 0) {
      const bit = bestCand & -bestCand;
      bestCand ^= bit;
      this.guesses++;
      this.g[br][bc] = 32 - Math.clz32(bit); // choose (bit index + 1)
      this.flip(br, bc, bit);
      if (this.solve()) return true; // explore
      this.flip(br, bc, bit); // unchoose
      this.g[br][bc] = 0;
    }
    return false;
  }
}

const s = new Sudoku(["8........", "..36.....", ".7..9.2..", ".5...7...", "....457..",
  "...1...3.", "..1....68", "..85...1.", ".9....4.."]);
if (!s.solve()) throw new Error("no solution");
const out = s.g.map((r) => r.join(""));
if (out[0] !== "812753649" || out[8] !== "796318452") throw new Error("wrong solution");
console.log(out.join("\n"));
console.log("guesses:", s.guesses);
Full propagation (naked + hidden singles) in Python

Instead of undoing changes, this version copies the domain dictionary before each guess, so a failed branch is simply thrown away. Copying 81 small integers is cheap next to the work saved.

UNITS = ([[(r, c) for c in range(9)] for r in range(9)] +                    # rows
         [[(r, c) for r in range(9)] for c in range(9)] +                    # columns
         [[(br + i, bc + j) for i in range(3) for j in range(3)]             # boxes
          for br in (0, 3, 6) for bc in (0, 3, 6)])
PEERS = {(r, c): {p for u in UNITS if (r, c) in u for p in u} - {(r, c)}
         for r in range(9) for c in range(9)}

def assign(dom: dict, cell: tuple, bit: int) -> bool:
    """Put digit `bit` in cell and propagate naked singles. False = contradiction."""
    dom[cell] = bit
    stack = [cell]
    while stack:
        cur = stack.pop()
        for p in PEERS[cur]:
            if dom[p] & dom[cur]:
                dom[p] &= ~dom[cur]
                if dom[p] == 0:
                    return False                      # a peer has no digit left
                if dom[p] & (dom[p] - 1) == 0:
                    stack.append(p)                   # naked single: propagate it too
    return True

def hidden_singles(dom: dict) -> bool:
    changed = True
    while changed:
        changed = False
        for unit in UNITS:
            for d in range(9):
                spots = [cell for cell in unit if dom[cell] >> d & 1]
                if not spots:
                    return False                      # digit d fits nowhere in this unit
                if len(spots) == 1 and dom[spots[0]] != 1 << d:
                    if not assign(dom, spots[0], 1 << d):
                        return False
                    changed = True
    return True

def solve(rows: list[str]) -> tuple[list[str] | None, int]:
    guesses = 0
    dom = {(r, c): 0x1FF for r in range(9) for c in range(9)}
    for r in range(9):
        for c in range(9):
            if rows[r][c] != "." and not assign(dom, (r, c), 1 << (int(rows[r][c]) - 1)):
                return None, 0

    def search(dom: dict) -> dict | None:
        nonlocal guesses
        if not hidden_singles(dom):
            return None
        open_cells = [x for x in dom if dom[x] & (dom[x] - 1)]   # more than one candidate
        if not open_cells:
            return dom
        cell = min(open_cells, key=lambda x: bin(dom[x]).count("1"))  # MRV
        m = dom[cell]
        while m:
            bit = m & -m
            m ^= bit
            guesses += 1
            child = dict(dom)                         # copy = free undo
            if assign(child, cell, bit):
                done = search(child)
                if done:
                    return done
        return None

    res = search(dom)
    if res is None:
        return None, guesses
    return ["".join(str(res[(r, c)].bit_length()) for c in range(9)) for r in range(9)], guesses

if __name__ == "__main__":
    easy = ["53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
            "7...2...6", ".6....28.", "...419..5", "....8..79"]
    hard = ["8........", "..36.....", ".7..9.2..", ".5...7...", "....457..",
            "...1...3.", "..1....68", "..85...1.", ".9....4.."]
    grid, g = solve(easy)
    assert grid[0] == "534678912" and g == 0
    grid, g = solve(hard)
    assert grid[0] == "812753649" and grid[8] == "796318452" and g == 172
    print("easy: 0 guesses, hard:", g, "guesses")

For the general version of this idea (exact cover with Knuth's Dancing Links), see Variations.

A classic backtracking problem: find if a word exists in a 2D grid by moving horizontally or vertically to adjacent cells.

Python:

def word_search(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])

    def backtrack(r: int, c: int, idx: int) -> bool:
        if idx == len(word):
            return True

        if (r < 0 or r >= rows or c < 0 or c >= cols or
                board[r][c] != word[idx]):
            return False

        # Mark as visited
        temp = board[r][c]
        board[r][c] = '#'

        found = (backtrack(r + 1, c, idx + 1) or
                 backtrack(r - 1, c, idx + 1) or
                 backtrack(r, c + 1, idx + 1) or
                 backtrack(r, c - 1, idx + 1))

        # Restore (backtrack)
        board[r][c] = temp
        return found

    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0):
                return True

    return False

Word search, analysed

The code above is the same template in disguise. The decision is "which neighbour holds the next letter". The shared state is the board itself: writing '#' into a cell is the choose (mark visited), and writing the letter back is the unchoose. Forget the restore and a later start cell finds a board full of # marks: a silent wrong answer.

  • Complexity: up to start cells; from each, the first step has 4 directions and every later step at most 3 (you cannot step back onto the cell you came from). So for a word of length , with recursion depth.
  • Cheap pruning that matters in practice: (1) if the word has more of some letter than the board, return false before searching; (2) if the last letter of the word is rarer on the board than the first, search for the reversed word, so the search fails earlier on most starts.
  • Many words at once (Word Search II): walk a trie of all the words alongside the grid DFS, so one walk serves every word sharing a prefix, and delete trie leaves once found.

Palindrome Partitioning

Problem: split a string into pieces so that every piece is a palindrome (reads the same backwards), and list every such split. For "aab" the answer is [["a","a","b"], ["aa","b"]].

The decision is "where does the next piece end?" Start at index start; try every end from start to n-1; if s[start..end] is a palindrome, take it and recurse from end + 1. When start == n the whole string has been cut: record the path. Checking "is this a palindrome" from scratch costs , so precompute a table pal[i][j] once with a small DP (a substring is a palindrome when its ends match and its inside is a palindrome); then every check is .

def partition(s: str) -> list[list[str]]:
    n = len(s)
    # pal[i][j] is True when s[i..j] reads the same both ways (O(n^2) DP, done once)
    pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])

    res: list[list[str]] = []
    path: list[str] = []

    def bt(start: int) -> None:
        if start == n:
            res.append(path[:])
            return
        for end in range(start, n):           # decision: where does the next piece end?
            if pal[start][end]:                # feasibility: only palindromic pieces
                path.append(s[start:end + 1])
                bt(end + 1)
                path.pop()

    bt(0)
    return res

assert partition("aab") == [["a", "a", "b"], ["aa", "b"]]
assert len(partition("aabb")) == 4
assert len(partition("aaaa")) == 8          # 2^(n-1): every cut is legal

Complexity: a string of length has gaps, and each gap is cut or not, so there are at most partitions ("aaaa" reaches all 8). Copying each costs : worst case, plus for the table. If the question is only "how few cuts?" (LeetCode 132), the answer is a DP, not a search; see Partition DP.

Generating Parentheses

Problem: list every balanced string of pairs of parentheses. For : ((())), (()()), (())(), ()(()), ()()().

Brute force writes all strings of ( and ) and keeps the balanced ones. Backtracking builds left to right and enforces two rules as it goes:

  • you may add ( while fewer than have been opened;
  • you may add ) only while closed < opened, so the prefix never closes more than it opened.

Both rules are feasibility tests, and together they are exact: every prefix that obeys them can be completed to a balanced string, so the search never reaches a dead end. Every leaf is an answer.

def generate_parenthesis(n: int) -> list[str]:
    res: list[str] = []
    path: list[str] = []

    def bt(opened: int, closed: int) -> None:
        if len(path) == 2 * n:
            res.append("".join(path))
            return
        if opened < n:                        # may still open a new pair
            path.append("(")
            bt(opened + 1, closed)
            path.pop()
        if closed < opened:                   # may close only what is open
            path.append(")")
            bt(opened, closed + 1)
            path.pop()

    bt(0, 0)
    return res

assert generate_parenthesis(3) == ["((()))", "(()())", "(())()", "()(())", "()()()"]
assert [len(generate_parenthesis(n)) for n in range(1, 9)] == [1, 2, 5, 14, 42, 132, 429, 1430]

The number of answers is the Catalan number , which grows like . Measured:

Answers Recursive callsBrute-force strings
1134
22816
352264
41464256
5421961,024
61326254,096
74292,05516,384
81,4306,91765,536

Since every leaf is an answer and every node has a leaf below it, total work is : proportional to the size of the output. That is the best any enumeration can do, and it is the goal to aim for with pruning in general. Catalan numbers also count binary trees with nodes and triangulations of a polygon; see Combinatorics.

The ladder: enumerate everything → backtracking → pruning and bitmasks

Take 8-Queens and climb from the dumbest correct program to a fast one. Every rung gives the same answer, 92.

Rung 1: enumerate all placements, then check

Put one queen in each row (already a small insight), try all column choices, and check each full board for column and diagonal clashes in . Roughly work. Hopeless beyond .

Rung 2: enumerate permutations

Two queens in one column is never allowed, so only permutations of columns can work: boards, each checked for diagonals. . A big improvement from one observation, but it still builds every complete board before checking.

Rung 3: backtracking with a check after every queen

Place queens row by row and test the new queen against the earlier ones before going deeper. A clash in row 2 kills every completion of that prefix at once. 2,057 calls for . With sets (or boolean arrays) for columns and the two diagonal families, each test is .

Rung 4: bitmasks and symmetry

Same tree, much cheaper nodes: the free columns of a row come from one expression, and the lowest one from free & -free. Add symmetry breaking (first queen in the left half only) and the tree halves: 1,029 calls.

RungIdeaWork for Why it is better
1. All placementsone queen per row, check at the end16,777,216 boards—
2. Permutationsalso one per column40,320 boardsuses a rule to shrink the space before searching
3. Backtrackingcheck after each queen2,057 callsrejects prefixes, not boards
4. Bitmasks + symmetrysame test, machine ops; half the tree1,029 callscheaper nodes, fewer nodes

The general lesson: move every check as early as possible. Each check you can apply to a prefix instead of a full candidate removes a whole subtree.

Correctness

Why does backtracking list every solution exactly once? The proof runs on the recursion tree, by induction (exactly as in Recursion & Mathematical Induction).

Setup. Define the tree : the root is the empty partial solution; the children of a node are the extensions of that the loop allows. The program is correct if three things hold.

Claim 1 (state restoration). If bt is called with shared state equal to , it returns with the state equal to .

Proof by induction on the height of the subtree. A leaf call changes nothing. For an internal node, each loop iteration does choose (state becomes ), calls bt (which, by the induction hypothesis on the smaller subtree, returns with ), then unchoose, which exactly reverses choose and gives back . After every iteration the state is , so it is at the end. ∎

Claim 2 (each node visited exactly once). bt called at node calls itself exactly once for each child of , and by Claim 1 each child sees the correct state. By induction on height, bt(v) visits every node of the subtree of exactly once. A tree has no cycles and a unique path from the root to each node, so no node is reached twice.

Claim 3 (the tree matches the answers one-to-one). This is problem specific and is where the templates differ:

  • Subsets: a node is a sequence of strictly increasing indices (the start = i + 1 rule). Every subset of has exactly one increasing ordering, so nodes and subsets are in bijection: each subset appears once.
  • Permutations: a leaf is a sequence of distinct indices (the used rule), and every permutation is exactly one such sequence.
  • Duplicates: among equal values, the skip rule only allows the leftmost unused copy (permutations) or the first equal sibling (subsets). So each distinct answer has exactly one canonical index sequence in the tree; all non-canonical copies are skipped.

Claim 4 (pruning is safe). A pruning test may cut node only if no solution lies in the subtree of (feasibility) or no solution there beats the best found (bounding). Under that condition, removing the subtree removes no answer that the unpruned search would have reported. If the test is merely a heuristic ("this probably will not work"), the claim fails, and so does correctness.

Claims 1–4 together give: every solution is reported, and reported exactly once.

Complexity

Count the nodes of the recursion tree and multiply by the work per node. Memory is the depth of the tree (the call stack plus the shared path), not its size, unless you store all the outputs.

TemplateNodesWork per nodeTotal timeExtra space (excluding output)
Subsets to copy the path
Combinations with the "room left" bound copy at leaves
Permutations loop over used
Generate parentheses, plus at leaves
N-Queensat most ; far fewer in practice with bitmasksmeasured: 35,539 calls at

Two facts about these numbers:

  • Output-sensitive bounds are the floor. If the answer has subsets of average size , merely writing it takes . Subsets, permutations and parentheses all meet that floor, so they are optimal for "list them all".
  • Pruning changes the practical count, not the worst case. Worst-case bounds for N-Queens or Sudoku stay exponential (general Sudoku on boards is NP-complete, Yato and Seta 2003), but the measured counts above show pruning skipping more than 99.98% of the placements for 8-Queens and propagation turning a 49,558-guess search into 172 guesses. Report both: the worst case for honesty, the measured count for reality. For estimating the size of a tree you cannot afford to walk, Knuth's 1975 random-probe estimator samples random root-to-leaf paths.

Common Complexity Analysis

ProblemSolutionsTime
Permutations of elements
Combinations
Subsets of elements
N-QueensVariable (exponential) upper bound
Sudoku (9x9)1 (unique) worst, much less with pruning

Backtracking vs Other Techniques

ApproachWhen to UseTime
BacktrackingNeed ALL solutions or a specific valid configurationExponential (but pruning helps)
Dynamic ProgrammingOptimal value (not all solutions), overlapping subproblemsPolynomial (usually)
GreedyLocal optimal leads to global optimalPolynomial
BFS/DFSGraph traversal, shortest path

TIP

If a problem asks "find the minimum/maximum" or "how many ways" — think DP first. If it asks "generate all" or "find a valid assignment" — think backtracking.

Real-world uses

  • SAT solvers (DPLL and CDCL). The DPLL procedure (Davis, Putnam, Logemann, Loveland, 1960–62) decides whether a boolean formula can be made true. It is exactly this lesson: pick an unassigned variable (a decision), set it, run unit propagation (a clause with one free literal forces that literal, the SAT version of a Sudoku naked single), and backtrack on a contradiction. Modern CDCL solvers (GRASP 1996, Chaff 2001, MiniSat 2003) add clause learning and non-chronological backjumping: on a conflict they record why it happened and jump back several levels at once. These solvers verify hardware, plan schedules and resolve software dependencies with millions of variables. See also 2-SAT & Graph Coloring for the special case that needs no search.
  • Regex engines. Perl, PCRE, Python's re, Java's java.util.regex and JavaScript engines match patterns by backtracking: at each |, * or ? they try one option and back up on failure. Features like backreferences need this. The cost is catastrophic backtracking: a pattern such as (a+)+b against a long string of as explores exponentially many ways to split the as. A regex like this took down Stack Overflow for 34 minutes on 20 July 2016, and a WAF rule caused Cloudflare's global outage on 2 July 2019. Engines such as RE2, Go's regexp and Rust's regex simulate an automaton instead and guarantee linear time (Russ Cox, "Regular Expression Matching Can Be Simple And Fast", 2007). Details in Regex Mastery and Regex Engines.
  • Constraint solvers. Gecode, Choco, MiniZinc back ends and Google OR-Tools' CP-SAT all combine propagation (shrinking domains), variable ordering heuristics like MRV, and backtracking or backjumping search, the same three ingredients as the Sudoku solver above. Timetabling, rostering and puzzle generation run on them.
  • Package managers. Choosing one version of every dependency so that all constraints hold is NP-complete in general. pip's resolver (since pip 20.3, 2020) backtracks over candidate versions; Cargo documents its resolver as a backtracking search; Dart's pub and the uv installer use PubGrub (Natalie Weizenbaum, 2018), a CDCL-style algorithm with conflict learning.
  • Parsers and logic programming. Recursive-descent parsers try one grammar alternative and fall back to the next on failure. Packrat parsing (Bryan Ford, 2002) memoises those attempts to guarantee linear time for PEGs, and CPython has used a PEG parser since 3.9 (PEP 617). Prolog runs every program as a depth-first search with chronological backtracking.
  • Exact cover. Sudoku, polyomino tilings and N-Queens are all exact-cover problems; Knuth's Algorithm X with "Dancing Links" (2000) is a backtracking search with an undo-friendly linked-list representation.

Pitfalls & edge cases

  • Forgetting to undo. Every mutation in choose needs its exact inverse in unchoose, in reverse order, on every path out of the loop body, including early continue or return. If you return True early (Sudoku, word search) it is fine to skip the undo, but only if no caller needs the state restored.
  • Recording a reference instead of a copy. res.append(path) stores the same list object every time; at the end every entry is the empty list. Use path[:], [...path], new ArrayList<>(path), or C++'s res.push_back(path) (which copies).
  • Mutable default arguments in Python. def bt(path=[]) creates one list when the function is defined and reuses it across calls, so a second top-level call starts with leftovers. Use path=None and create the list inside, or a closure as in this lesson.
  • Sharing vs copying, decided on purpose. Copy-on-call (pass path + [x]) needs no undo but costs per call; shared-with-undo costs . Both are correct. Mixing them by accident (copying some state, sharing other state) is the classic bug.
  • Modifying a collection while iterating it. The original Python permutations iterates list(remaining) for exactly this reason; iterating the live set while removing from it raises an error.
  • Duplicate skip with i > 0 instead of i > start (subsets/combinations): this also blocks going deeper with an equal value, so [2, 2] disappears.
  • Wrong base case placement. In subsets, record at every node. In permutations and combinations, only at full length. Recording at the wrong place gives too many or too few answers.
  • Edge cases: empty input (subsets returns [[]], one answer, not zero); or in combinations; N-Queens for has zero solutions; a target of 0 in combination sum returns [[]].
  • Recursion depth. Depth equals the number of decisions: 81 for Sudoku, for permutations, the word length in word search. Python's limit of 1000 is usually enough, but grid flood-style backtracking over 10⁶ cells is not; use an explicit stack.
  • Exponential output. subsets is about a million lists, roughly 10 million integers. Check the expected output size against memory before you start.

Variations

  • Find one vs find all vs count vs best. Return True up the stack on the first solution (Sudoku); collect all (subsets); return counts instead of lists (N-Queens II, no copying); keep a running best with bounding (branch and bound).
  • Iterative backtracking with an explicit stack of (state, next-choice index) frames: same tree, no recursion limit. See Converting recursion to iteration.
  • Bitmask enumeration instead of recursion for subsets: for mask in range(1 << n). Simple, but cannot prune. Gosper's hack steps through all -bit masks for combinations.
  • Next-permutation (lexicographic successor, std::next_permutation) lists permutations without recursion and handles duplicates for free.
  • Memoised backtracking = DP. If the future of a partial solution depends only on a small summary (index, remaining sum), cache by that summary. Word Break II, "count the ways" and Bitmask DP grow from here.
  • Meet in the middle. Split items in half, enumerate choices per half, and combine with sorting or hashing: subset sum for goes from to about per half.
  • Exact cover with Dancing Links (Knuth's Algorithm X): always branch on the column with fewest candidates (MRV again), with undo via relinked list nodes.
  • Backjumping and learning (CDCL): on failure jump to the decision that actually caused it and store a clause so the same conflict never repeats.
  • Randomised restarts and local search for huge instances where a complete search is hopeless: see Heuristics & Metaheuristics.

Practice ladder

Each problem is described in my own words; follow the link for the full statement. Easy to hard.

1. Subsets (LeetCode 78) — List every subset of distinct numbers. The subsets template, verbatim.

Hint

Record at every node; loop i from start; recurse with i + 1.

2. Permutations (LeetCode 46) — List every ordering of distinct numbers.

Hint

used[] array; record at length . Alternative: swap nums[k] with each nums[i] for i >= k, recurse on k + 1, swap back.

3. Combinations (LeetCode 77) — Every way to choose numbers from 1 to .

Hint

Stop the loop at n - (k - len(path)) + 1: past that, not enough numbers remain.

4. Creating Strings (CSES 1622) — Print every distinct rearrangement of a short string, in sorted order, with its count. Letters may repeat.

Hint

Sort the letters, then the duplicate-skipping permutation template outputs distinct strings already in sorted order. Or count letters and branch on "which letter next" while counts remain.

5. Generate Parentheses (LeetCode 22) — Every balanced string with pairs.

Hint

Open while opened < n; close while closed < opened. No dead ends. The code in this lesson is a full solution.

6. Subsets II (LeetCode 90) — Subsets when the input may repeat values; no duplicate subsets.

Hint

Sort; skip nums[i] == nums[i-1] when i > start. The code in the templates section is a full solution.

7. Permutations II (LeetCode 47) — Distinct orderings of a list with repeats.

Hint

Sort; skip when the equal left neighbour is unused (not used[i-1]).

8. Combination Sum (LeetCode 39) — Pick numbers (reuse allowed) that add to a target.

Hint

Recurse with i (not i + 1); sort and break when a value exceeds the remainder.

9. Combination Sum II (LeetCode 40) — Same, but each element used at most once and the input has repeats.

Solution

Sort; recurse with i + 1; skip equal siblings; break when too big.

def combination_sum2(cands, target):
    cands = sorted(cands)
    res, path = [], []

    def bt(start, remaining):
        if remaining == 0:
            res.append(path[:])
            return
        for i in range(start, len(cands)):
            if i > start and cands[i] == cands[i - 1]:
                continue                     # equal sibling: same subtree again
            if cands[i] > remaining:
                break
            path.append(cands[i])
            bt(i + 1, remaining - cands[i])  # i + 1: each element once
            path.pop()

    bt(0, target)
    return res

assert combination_sum2([10, 1, 2, 7, 6, 1, 5], 8) == [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

10. Palindrome Partitioning (LeetCode 131) — Every split of a string into palindromic pieces.

Hint

Decide where the next piece ends; precompute pal[i][j]. The code in this lesson is a full solution.

11. Word Search (LeetCode 79) — Does the word appear as a path of adjacent cells, each used once?

Hint

Mark with #, recurse into 4 neighbours, restore. Prune with letter counts and by reversing the word if its last letter is rarer.

12. Chessboard and Queens (CSES 1624) — Count ways to place 8 queens on an 8×8 board where some squares are reserved.

Solution

N-Queens with one extra feasibility test: a reserved square is never free. With bitmasks, precompute a "blocked" mask per row and AND it out.

def count_queens(board):              # board: 8 strings of '.' (free) and '*' (reserved)
    n, full = 8, (1 << 8) - 1
    blocked = [sum(1 << c for c in range(n) if row[c] == "*") for row in board]

    def place(r, cols, diag, anti):
        if r == n:
            return 1
        free = full & ~(cols | diag | anti | blocked[r])
        total = 0
        while free:
            bit = free & -free
            free ^= bit
            total += place(r + 1, cols | bit, ((diag | bit) << 1) & full, (anti | bit) >> 1)
        return total

    return place(0, 0, 0, 0)

assert count_queens(["........"] * 8) == 92
sample = ["........", "........", "..*.....", "........", "........", ".....**.", "...*....", "........"]
assert count_queens(sample) == 65

13. N-Queens II (LeetCode 52) and N-Queens (LeetCode 51) — Count the solutions; then print the boards.

Hint

The bitmask counter in this lesson solves 52 directly. For 51, also keep the chosen column per row and build strings at the leaves.

14. Sudoku Solver (LeetCode 37) — Fill a 9×9 board in place.

Hint

Row/column/box bitmasks plus MRV. The four-language solver in this lesson is a full solution after converting the board format.

15. Word Search II (LeetCode 212) — Find every word from a dictionary that appears in the grid.

Solution

Build a trie of the words. Run one grid DFS per start cell, walking the trie in step with the grid; a trie node marked "end of word" yields an answer. Remove a word's end marker once found so it is reported once, and prune trie branches that become empty.

def find_words(board, words):
    trie = {}
    for w in words:
        node = trie
        for ch in w:
            node = node.setdefault(ch, {})
        node["$"] = w                        # end-of-word marker holds the word
    R, C, found = len(board), len(board[0]), []

    def dfs(r, c, parent):
        ch = board[r][c]
        node = parent[ch]
        if "$" in node:
            found.append(node.pop("$"))      # report once
        board[r][c] = "#"                    # choose: mark visited
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < R and 0 <= nc < C and board[nr][nc] in node:
                dfs(nr, nc, node)
        board[r][c] = ch                     # unchoose: restore
        if not node:
            parent.pop(ch)                   # prune exhausted trie branch

    for r in range(R):
        for c in range(C):
            if board[r][c] in trie:
                dfs(r, c, trie)
    return found

grid = [list("oaan"), list("etae"), list("ihkr"), list("iflv")]
assert sorted(find_words(grid, ["oath", "pea", "eat", "rain"])) == ["eat", "oath"]

Practice Problems

ProblemPatternDifficulty
SubsetsSubset generationMedium
PermutationsPermutation generationMedium
CombinationsCombination generationMedium
Combination SumCombination + pruningMedium
Letter Combinations of Phone NumberMulti-way branchingMedium
Palindrome PartitioningString partition + palindrome checkMedium
Generate ParenthesesConstraint: open >= closeMedium
Word SearchGrid backtrackingMedium
N-QueensConstraint satisfactionHard
Sudoku SolverConstraint satisfactionHard
Word Search IITrie + backtrackingHard
Expression Add OperatorsString partition + evaluationHard

Common mistakes & interview follow-ups

"What is the time complexity of your subsets / permutations solution?" Count nodes times work per node: and . Say that this matches the output size, so no algorithm that lists them all can do asymptotically better.

"Your input now has duplicates." Sort, then skip equal siblings (i > start) for subsets and combinations, or require left-to-right use of equal values (not used[i-1]) for permutations. Explain why the rule is about siblings, not depth.

"Can you do it without recursion?" Subsets: iterate masks 0 .. 2^n - 1, or start from [[]] and for each element append it to every existing subset. Permutations: repeated next-permutation. General backtracking: an explicit stack of frames.

"Only count the N-Queens solutions; make it fast." Bitmasks, no board, no copying, plus left-half symmetry. Mention that the counts are known only up to (computed in 2016 with massive parallel search), which shows how fast the tree grows.

"Return just one Sudoku solution as fast as possible." Bitmask domains, MRV, propagation (naked and hidden singles), and stop at the first solution. Mention that a pure CSP framing generalises (Dancing Links for exact cover, or hand it to a SAT/CP solver).

"Your regex service timed out on one input. Why?" Catastrophic backtracking: nested quantifiers like (a+)+ give exponentially many ways to match. Fixes: rewrite the pattern to be unambiguous, use atomic groups or possessive quantifiers, set a match timeout, or switch to an automaton engine such as RE2.

"When would you choose DP over backtracking here?" When the question asks for a count or an optimum and partial solutions with the same summary (index, remaining sum) have the same future. Then memoise on that summary.

Mistakes interviewers watch for: appending path without copying; forgetting to undo one of several state changes; i > 0 instead of i > start in the duplicate rule; not sorting before deduplication; recording subsets only at the leaves; looping to n instead of n - need + 1 in combinations (correct, but they will ask about pruning); using a default mutable argument in Python.

Try It Yourself

Problem 1: Generate all permutations of [1, 2, 3].

Solution

Using the backtracking template (choose, explore, unchoose):

  • Start with path=[], remaining={1,2,3}
  • Choose 1: path=[1], remaining={2,3}
    • Choose 2: path=[1,2], remaining={3} → [1,2,3]
    • Choose 3: path=[1,3], remaining={2} → [1,3,2]
  • Choose 2: path=[2], remaining={1,3}
    • Choose 1: [2,1,3]
    • Choose 3: [2,3,1]
  • Choose 3: path=[3], remaining={1,2}
    • Choose 1: [3,1,2]
    • Choose 2: [3,2,1] Answer: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] (6 permutations = 3!)

Problem 2: Generate all subsets of [1, 2, 3].

Solution

At each element, decide to include or exclude:

  • [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] Using the iterative backtracking approach:
  • Start: index=0, path=[] → record []
  • Add 1: path=[1] → record [1]. Add 2: [1,2] → record. Add 3: [1,2,3] → record. Pop 3. Pop 2.
  • Add 3: [1,3] → record. Pop 3. Pop 1.
  • Add 2: [2] → record. Add 3: [2,3] → record. Pop 3. Pop 2.
  • Add 3: [3] → record. Pop 3. Answer: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]] (8 subsets = )

Problem 3: Solve the 4-Queens problem: place 4 queens on a 4x4 board so no two attack each other.

Solution

Place queens row by row, tracking occupied columns and diagonals:

  • Row 0: try col 0 → blocked later. Try col 1 → works.
  • Row 1: try col 3 → works (col 3 free, diags 1-3=-2 and 1+3=4 free).
  • Row 2: try col 0 → works (col 0 free, diags 2-0=2 and 2+0=2 free).
  • Row 3: try col 2 → works (col 2 free, diags 3-2=1 and 3+2=5 free). Solution:
. Q . .
. . . Q
Q . . .
. . Q .

There are 2 solutions for 4-Queens.

Problem 4: Find all combinations of [2, 3, 6, 7] that sum to 7 (elements can be reused).

Solution

Using backtracking with pruning (sort first: [2, 3, 6, 7]):

  • Start with 2: remaining=5. Pick 2 again: remaining=3. Pick 2: remaining=1. Pick 2: remaining=-1 → prune. Pick 3: remaining=-2 → prune. Backtrack.
  • Path [2,2]: remaining=3. Pick 3: remaining=0 → [2,2,3] found.
  • Path [2]: remaining=5. Pick 3: remaining=2. Pick 3: remaining=-1 → prune. Backtrack.
  • Path [3]: remaining=4. Pick 3: remaining=1. No valid picks → prune. Backtrack.
  • Path [7]: remaining=0 → [7] found. Answer: [[2,2,3], [7]]

Problem 5: Use backtracking to check if the word "ABCCED" exists in the grid:

A B C E
S F C S
A D E E
Solution

Start from each cell matching 'A':

  • Cell (0,0)='A' → (0,1)='B' → (1,1)='F'? No. → (0,0) not adjacent to 'B' except (0,1). Try (0,1)='B' → (0,2)='C' → (1,2)='C' → (2,2)='E' → (2,1)='D' → found! Path: (0,0)A → (0,1)B → (0,2)C → (1,2)C → (2,2)E → (2,1)D Answer: true -- the word exists in the grid.

Quick Quiz

1. What is the time complexity of generating all subsets of a set with elements?

  • a)
  • b)
  • c)
  • d)
Answer

c) — There are subsets, and each takes to copy into the result list.

2. What is the key difference between backtracking and brute force?

  • a) Backtracking is always faster
  • b) Backtracking prunes branches that cannot lead to valid solutions, avoiding unnecessary exploration
  • c) Brute force cannot solve constraint satisfaction problems
  • d) Backtracking uses more memory
Answer

b) Backtracking prunes branches that cannot lead to valid solutions, avoiding unnecessary exploration — Backtracking is brute force with early termination. When a partial solution violates constraints, the entire subtree is skipped.

3. In the N-Queens problem, how do you check diagonal conflicts in ?

  • a) Check all previously placed queens
  • b) Use sets tracking row - col and row + col values
  • c) Use a 2D boolean array for the board
  • d) Compare absolute differences of coordinates
Answer

b) Use sets tracking row - col and row + col values — All cells on the same diagonal share the same row - col value (for one diagonal direction) or row + col value (for the other). Storing these in sets gives conflict checking.

4. When should you use backtracking instead of dynamic programming?

  • a) When you need the optimal value only
  • b) When you need to generate all valid solutions or find a specific valid configuration
  • c) When the problem has overlapping subproblems
  • d) When the input size is very large
Answer

b) When you need to generate all valid solutions or find a specific valid configuration — DP finds optimal values efficiently but does not enumerate all solutions. Backtracking systematically explores all possibilities and is the right tool when you need to list or count all valid configurations.

5. Why is sorting the input often the first step in backtracking problems?

  • a) It makes the recursion faster
  • b) It enables pruning (skip remaining candidates when current exceeds target) and duplicate avoidance
  • c) It reduces memory usage
  • d) It is required by the backtracking template
Answer

b) It enables pruning (skip remaining candidates when current exceeds target) and duplicate avoidance — With sorted input, once a candidate exceeds the remaining budget you can break (all subsequent candidates are larger). Sorting also groups duplicates together, making it easy to skip duplicate branches.

6. In the subsets trace for [1, 2, 3], how many choose events are there, and why?

Answer
  1. The recursion tree has 8 nodes (one per subset), and a tree with 8 nodes has 7 edges. Each edge is walked down once (choose) and up once (unchoose).

7. Why does the bitmask N-Queens code need no explicit "unchoose"?

Answer

The new masks are passed as arguments (by value). The caller's cols, diag and anti never change, so returning from the call restores the state automatically.

8. A Sudoku cell has candidates {4, 7}; another has {1, 2, 5, 8, 9}. Under MRV, which do you branch on, and why?

Answer

The {4, 7} cell. It has the fewest remaining values, so a guess there is right half the time, and if both values fail the branch dies after only two tries. This is the "fail-first" principle.

Further Reading

Sources

  • Donald E. Knuth, The Art of Computer Programming, Volume 4B (2022), §7.2.2 "Backtrack programming" (including Dancing Links and the estimation of tree sizes).
  • Solomon W. Golomb and Leonard D. Baumert, "Backtrack Programming", Journal of the ACM 12(4), 1965. R. J. Walker, "An enumerative technique for a class of combinatorial problems", Proc. Symposia in Applied Mathematics 10, 1960.
  • Donald E. Knuth, "Estimating the efficiency of backtrack programs", Mathematics of Computation 29, 1975; and "Dancing Links", 2000, arXiv:cs/0011047.
  • Steven S. Skiena, The Algorithm Design Manual, 3rd ed. (2020), Chapter 9 "Combinatorial Search".
  • Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, 4th ed. — Chapter 6 "Constraint Satisfaction Problems" (MRV, forward checking, propagation).
  • Peter Norvig, "Solving Every Sudoku Puzzle".
  • Martin Davis, George Logemann and Donald Loveland, "A machine program for theorem-proving", Communications of the ACM 5(7), 1962; João Marques-Silva and Karem Sakallah, "GRASP: A Search Algorithm for Propositional Satisfiability", IEEE Transactions on Computers 48(5), 1999.
  • Russ Cox, "Regular Expression Matching Can Be Simple And Fast", 2007. Stack Overflow status blog, "Outage Postmortem – July 20, 2016". Cloudflare, "Details of the Cloudflare outage on July 2, 2019".
  • Takayuki Yato and Takahiro Seta, "Complexity and Completeness of Finding Another Solution and Its Application to Puzzles", IEICE Transactions E86-A(5), 2003 (Sudoku is NP-complete).
  • OEIS A000170 (number of N-Queens solutions) and A000108 (Catalan numbers).
  • cp-algorithms, Generating all K-combinations.

Lessons: previous — Paradigms overview · next — Divide & Conquer · module — Paradigms · course — DSA: Zero to Mastery.

Related Archon pages: Recursion & Mathematical Induction · Complexity Analysis · DFS · 2-SAT & Graph Coloring · Greedy Algorithms · Bit Manipulation · Tries · Bitmask DP · Partition DP.