Backtracking Algorithms

The Backtracking Template

Every backtracking solution is the same recursive skeleton with a few blanks filled in. Read it once here, and the three problems that follow will each be nothing more than this template with specific answers plugged in for three questions: what does a complete solution look like, what choices can extend the current partial solution, and which of those choices are allowed?

# The shared skeleton. Each problem in this lesson is this template
# with the blanks filled in: what counts as complete, what the candidate
# choices are, and which of those choices are allowed.
def backtrack(state):
    if is_complete(state):
        record(state)             # save a copy of the finished solution
        return

    for choice in candidates(state):
        if not allowed(choice, state):
            continue              # prune: skip a choice that cannot lead to a valid solution
        state.append(choice)      # choose
        backtrack(state)          # explore everything that follows from it
        state.pop()               # un-choose, then try the next candidate

The three comments, choose, explore, un-choose, are the heart of it. Appending a choice commits to it, the recursive call explores every solution that starts with that commitment, and popping it back off restores the state exactly as it was so the next candidate starts clean. That single shared list is why backtracking is so memory-efficient: at any instant it holds just one partial solution, never the whole search tree. The allowed check is the optional fourth blank, the prune, and whether a problem even has a meaningful prune is exactly what separates a mechanical enumeration from a genuinely smart search, as the three examples below show.

Generating Subsets (the Power Set)

Subsets is the template at its simplest: every choice is always allowed, so there's no prune at all. The one twist is in the completion test: a subset can stop growing at any point, so instead of recording only at a leaf, each call records current the instant it begins, before appending anything. That makes every node in the recursion tree, not just the leaves, a complete and valid subset:

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

    def backtrack(start: int) -> None:
        result.append(current.copy())        # every partial state is itself a valid subset
        for i in range(start, len(nums)):
            current.append(nums[i])           # choose
            backtrack(i + 1)                  # explore
            current.pop()                     # un-choose (the "backtrack" step)

    backtrack(0)
    return result

print(subsets([1, 2, 3]))
print(len(subsets([1, 2, 3])))

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
8

With n numbers, the recursion tree has exactly 2ⁿ nodes, one per subset, since each of the n numbers independently doubles the count. There's no pruning possible here: every subset is a valid answer, so the algorithm's work is inherently exponential no matter how it's organized.

Generating Permutations

Permutations fills in two of the template's blanks. The completion test now fires only when current holds all n numbers, since a partial ordering is not yet an answer, and the allowed rule skips any number already placed, tracked by the used array. That used check is bookkeeping to honor the definition of a permutation, not a real prune: every ordering the recursion is allowed to start still finishes as a valid answer, so no branch is ever wasted:

def permutations(nums: list[int]) -> list[list[int]]:
    result = []
    current = []
    used = [False] * len(nums)

    def backtrack() -> None:
        if len(current) == len(nums):
            result.append(current.copy())     # only complete orderings count as an answer
            return
        for i in range(len(nums)):
            if used[i]:
                continue                       # prune: this number is already placed
            used[i] = True
            current.append(nums[i])
            backtrack()
            current.pop()
            used[i] = False

    backtrack()
    return result

print(permutations([1, 2, 3]))
print(len(permutations([1, 2, 3])))

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
6

The first position has n choices, the second has n - 1 remaining choices, and so on, giving n! total orderings. Just like subsets, no partial ordering is ever a dead end: the branching factor shrinks naturally as numbers get used up, but every path still reaches a valid permutation, so the leaf count is exactly n!.

A Constraint Problem: The N-Queens Puzzle

Place n chess queens on an n × n board so that no two attack each other, no shared row, column, or diagonal. Placing one queen per row by construction rules out row conflicts entirely, so only columns and the two diagonal directions need tracking. A queen at (row, col) shares a "\\" diagonal with every square where row - col is the same, and a "/" diagonal with every square where row + col is the same, so three sets are enough to check any conflict in O(1):

def solve_n_queens(n: int) -> list[list[int]]:
    solutions = []
    columns = set()
    diagonals = set()          # constant along a "\" diagonal: row - col
    anti_diagonals = set()     # constant along a "/" diagonal: row + col
    placement = [-1] * n       # placement[row] = column of the queen in that row

    def backtrack(row: int) -> None:
        if row == n:
            solutions.append(placement.copy())
            return
        for col in range(n):
            if col in columns or (row - col) in diagonals or (row + col) in anti_diagonals:
                continue        # prune: this column is already under attack
            columns.add(col)
            diagonals.add(row - col)
            anti_diagonals.add(row + col)
            placement[row] = col
            backtrack(row + 1)
            columns.remove(col)
            diagonals.remove(row - col)
            anti_diagonals.remove(row + col)

    backtrack(0)
    return solutions

solutions = solve_n_queens(4)
print(solutions)
print(len(solutions))

[[1, 3, 0, 2], [2, 0, 3, 1]]
2

Those two lists are the only two ways to place four queens on a 4x4 board with none attacking another. Since placement[row] is the column of that row's queen, each list draws directly onto a board:

Figure 2: The two solutions to the 4-Queens puzzle. In each, no two queens share a row, a column, or a diagonal. Notice the second board is the mirror image of the first.

Now the allowed check finally earns its keep. Unlike subsets and permutations, most branches here are dead ends: a queen placed in an attacked column can never be part of a valid board, so continue prunes that entire subtree instead of recursing into a branch already known to fail. This is the first genuine constraint-satisfaction problem in the lesson, and the first place pruning actually changes how much work gets done.

Why Pruning Matters

In subsets and permutations, every branch the rules allow still reaches a valid answer, so there is nothing to prune. N-Queens is the opposite: a placement can look fine locally and still doom the rest of the board, and pruning is what abandons those dead ends early. Comparing the exact same recursive structure with and without the conflict check, counting every loop iteration as one "node visited", shows exactly how much that pruning saves on an 8x8 board:

import math

def count_unpruned_nodes(n: int) -> int:
    """Every column at every row, no conflict checking at all."""
    nodes = 0
    def recurse(row: int) -> None:
        nonlocal nodes
        if row == n:
            return
        for col in range(n):
            nodes += 1
            recurse(row + 1)
    recurse(0)
    return nodes

def count_pruned_nodes(n: int) -> int:
    """Same recursion, but skips a branch the instant a conflict is found."""
    nodes = 0
    columns, diagonals, anti_diagonals = set(), set(), set()
    def backtrack(row: int) -> None:
        nonlocal nodes
        if row == n:
            return
        for col in range(n):
            nodes += 1
            if col in columns or (row - col) in diagonals or (row + col) in anti_diagonals:
                continue
            columns.add(col); diagonals.add(row - col); anti_diagonals.add(row + col)
            backtrack(row + 1)
            columns.remove(col); diagonals.remove(row - col); anti_diagonals.remove(row + col)
    backtrack(0)
    return nodes

n = 8
print("Unpruned nodes visited:", count_unpruned_nodes(n))
print("Pruned nodes visited:  ", count_pruned_nodes(n))
print("Brute-force permutations checked at the end:", math.factorial(n))

Unpruned nodes visited: 19173960
Pruned nodes visited:   15720
Brute-force permutations checked at the end: 40320

Checking conflicts before recursing, rather than only at the end, cuts the search from over 19 million nodes down to under 16 thousand, over a thousandfold reduction. The worst-case bound for N-Queens is still O(n!), the pruning doesn't change what could theoretically happen in the rare case where almost nothing gets pruned, but it changes what actually happens dramatically. This is the core lesson of backtracking: the same exhaustive-search shape can range from useless to highly practical depending entirely on how early invalid branches get detected and abandoned.

Complexity at a Glance

The extra n factor in the subsets and permutations time bounds accounts for the cost of copying current into the result each time a valid answer is found. Extra space excludes the output list itself and counts only the recursion stack, which never grows past one frame per element being placed.