Backtracking

Backtracking is building a solution one piece at a time, and the moment a partial solution cannot possibly grow into a valid one, abandoning it and trying something else.

It is depth-first search over a decision tree — each level is one choice to make, each branch one option, each node a partial state, and each leaf either a complete answer or a dead end. The “backtrack” is simply undoing the last choice and trying the next sibling. Suppose you want every subset of {A, B, C}: at each element you decide include or skip, and the eight leaves are the eight subsets.

The template never changes

Every backtracking algorithm is the same three-move loop — choose, explore, un-choose:

def backtrack(state):
    if is_complete(state):
        record(state); return
    for choice in choices(state):
        if is_valid(state, choice):       # prune before recursing
            make(state, choice)           # choose
            backtrack(state)              # explore
            undo(state, choice)           # un-choose

The undo is what makes it backtracking rather than plain recursion: it restores the shared state exactly, so the next iteration starts from a clean slate. The only parts you ever swap are the validity check and what counts as complete. And that validity check — pruning — is everything: skip a branch the instant it cannot lead anywhere, and an exponential search becomes explorable; skip nothing, and you are brute-forcing every candidate.

Subsets: no pruning, genuinely 2ⁿ

Subsets are the case with no pruning, because every partial subset is valid — so the work is honestly 2ⁿ:

def all_subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(list(current))          # every prefix is a valid subset
        for i in range(start, len(nums)):
            current.append(nums[i])           # choose
            backtrack(i + 1, current)         # explore
            current.pop()                     # un-choose
    backtrack(0, [])
    return result

print("subsets of [1,2,3,4]:", len(all_subsets([1, 2, 3, 4])))
for n in range(1, 6):
    print(f"  n={n}: {len(all_subsets(list(range(n))))} subsets  (2^{n} = {2**n})")

subsets of [1,2,3,4]: 16
  n=1: 2 subsets  (2^1 = 2)
  n=2: 4 subsets  (2^2 = 4)
  n=3: 8 subsets  (2^3 = 8)
  n=4: 16 subsets  (2^4 = 16)
  n=5: 32 subsets  (2^5 = 32)

N-Queens: where pruning earns its keep

Place n queens on an n×n board with none attacking another. The tree has n rows and n columns per row — nⁿ placements without pruning. But reject a column the instant it shares a column or diagonal with a queen already placed, and the search collapses to something you can run in milliseconds. Three sets give O(1) conflict checks:

def count_queens(n):
    cols, diag1, diag2 = set(), set(), set()
    count = 0
    def place(row):
        nonlocal count
        if row == n:
            count += 1; return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue                                  # prune: under attack
            cols.add(col); diag1.add(row - col); diag2.add(row + col)   # choose
            place(row + 1)                                # explore
            cols.discard(col); diag1.discard(row - col); diag2.discard(row + col)  # un-choose
    place(0)
    return count

for n in range(4, 11):
    print(f"{n}-Queens: {count_queens(n)} solutions")

4-Queens: 2 solutions
5-Queens: 10 solutions
6-Queens: 4 solutions
7-Queens: 40 solutions
8-Queens: 92 solutions
9-Queens: 352 solutions
10-Queens: 724 solutions

For 8 queens there are just 92 solutions among 16,777,216 raw placements — pruning lets you skip almost all of the dead ones. Worst-case backtracking is still exponential (you cannot beat an exponential answer space), but tight, early validity checks shrink the effective branching factor enormously. The same skeleton, with a constraint check swapped in, solves Sudoku (only legal digits per cell) and word search (in-bounds, unvisited, next letter matches).

Practice