12.2 Backtracking

Prerequisites: Recursion and Divide and Conquer. This lesson uses the N-Queens problem, permutations with duplicates, and subsets to practice representing choices, checking constraints, and pairing each choice with its undo operation.

Branches Won't Preserve State for You

A backtracking implementation must first answer four questions:

1. What state does the current path maintain?
2. What are the available candidate choices at the next step?
3. Which constraints can eliminate candidates early (pruning)?
4. Under what condition does the current path form a valid solution?

If using a mutable path, modifications at each recursive level must be undone upon return. When storing results, the path must be copied, otherwise, all results may point to the same final list.

Three Executable Examples

n must be a non-negative integer. The other functions accept iterables, sort copies, and deduplicate by value. Ordering and equality must agree; NaN and mutually incomparable types are outside the contract. Result lists are shallow copies that still refer to the original elements. Distinct objects that compare equal count as the same value.

def solve_n_queens(n):
    if not isinstance(n, int):
        raise TypeError("n must be an integer")
    if n < 0:
        raise ValueError("n must be non-negative")

    solutions = []
    columns = set()
    descending = set()  # row - column
    ascending = set()   # row + column
    placement = []

    def search(row):
        if row == n:
            solutions.append([
                "." * column + "Q" + "." * (n - column - 1)
                for column in placement
            ])
            return

        for column in range(n):
            down = row - column
            up = row + column
            if (
                column in columns
                or down in descending
                or up in ascending
            ):
                continue

            placement.append(column)
            columns.add(column)
            descending.add(down)
            ascending.add(up)

            search(row + 1)

            ascending.remove(up)
            descending.remove(down)
            columns.remove(column)
            placement.pop()

    search(0)
    return solutions

def unique_permutations(values):
    items = sorted(values)
    used = [False] * len(items)
    path = []
    result = []

    def search():
        if len(path) == len(items):
            result.append(path.copy())
            return

        for index, value in enumerate(items):
            if used[index]:
                continue
            if (
                index > 0
                and items[index] == items[index - 1]
                and not used[index - 1]
            ):
                continue

            used[index] = True
            path.append(value)
            search()
            path.pop()
            used[index] = False

    search()
    return result

def unique_subsets(values):
    items = sorted(values)
    path = []
    result = []

    def search(start):
        result.append(path.copy())
        for index in range(start, len(items)):
            if index > start and items[index] == items[index - 1]:
                continue
            path.append(items[index])
            search(index + 1)
            path.pop()

    search(0)
    return result

if __name__ == "__main__":
    assert len(solve_n_queens(4)) == 2
    assert solve_n_queens(1) == [["Q"]]
    assert solve_n_queens(0) == [[]]

    assert unique_permutations([1, 1, 2]) == [
        [1, 1, 2],
        [1, 2, 1],
        [2, 1, 1],
    ]
    assert unique_permutations([]) == [[]]

    assert unique_subsets([1, 2, 2]) == [
        [],
        [1],
        [1, 2],
        [1, 2, 2],
        [2],
        [2, 2],
    ]
    assert unique_subsets([]) == [[]]

    print("Backtracking check passed")

All three functions define the semantic meaning of empty input as "an empty choice," returning [[]] instead of "no solution." The N-Queens n=0 likewise follows this convention. If a project adopts an alternative definition, it must be consistently changed in both the interface and the tests.

N Queens: Transforming Scanning into Set Constraints

Each row contains exactly one queen, so the path only needs to track the column selected in each row. Two queens conflict if and only if:

• They share the same column;
• row - column is the same, meaning they lie on the same descending diagonal;
• row + column is the same, meaning they lie on the same ascending diagonal.

These three sets reduce the average cost of a conflict check to nearly O(1), avoiding the need to scan all previous rows on every iteration. When making a selection, we add the column and both diagonal identifiers; upon backtracking, we remove them in reverse order. The order of processing is not mathematically required, but it simplifies the verification of state restoration step by step.

Ignoring diagonal constraints, the total number of partial column permutations is O(n!). This implementation still scans n columns at every non-leaf node, so O(n·n!) is a conservative search-time bound; counting leaves alone misses this work. With S solutions, constructing and retaining the boards adds Θ(S·n²) time and space. The search path, sets, and stack use another O(n) space. This analysis assumes expected O(1) set operations.

Permutations: Skipping Duplicate Values Within the Same Layer

For a sorted [1, 1, 2], the two 1s are indistinguishable in value. The condition:

items[index] == items[index - 1] and not used[index - 1]

means "if the previous identical value hasn't been selected in the current path, skip the duplicate to avoid branching from a redundant copy." If the previous copy has already been used in the current path, the next instance is still valid and thus [1, 1, 2] will not be incorrectly pruned.

This condition must rely simultaneously on sorting and used. A rule like "skip adjacent duplicates" would miss valid permutations; without sorting, identical values would be scattered and unable to be grouped together.

If all n values are distinct, the output consists of n! permutations, each of length n. Simply copying the results requires Θ(n·n!) time and space. Backtracking cannot avoid that output cost. The implementation also scans the full input at each level. With many duplicates, output count alone therefore understates the work: n equal values produce one permutation but still require Θ(n²) candidate scans. Excluding results, the sorted copy, path, used array, and stack use O(n) space.

Subsets: start Prevents Reordering

Subsets do not consider the order of selection. The recursive parameter start enforces selection only from later positions, so [1, 2] and [2, 1] are not generated separately.

The deduplication condition index > start is crucial: it skips only equal candidates within the same recursive layer. After descending into a deeper layer, the second 2 can still be selected, enabling the generation of [2, 2].

A set of n distinct elements has 2^n subsets. The total number of elements across all outputs is Θ(n·2^n). Pruning eliminates impossible or redundant branches; it cannot make listing all results take polynomial time. Excluding results, the subset search also uses O(n) space for its copy, path, and stack. All three implementations can recurse to depth n, so Python’s recursion limit or result memory can constrain large inputs.

When Is Pruning Safe?

Pruning must come from provable constraints. For example, if all candidate values are non-negative and the current sum already exceeds the target, we can safely stop further exploration. However, if negative values are allowed among candidates, subsequent elements could reduce the sum back below the target, making the same pruning condition invalid.

In practice, start with a small, easily verifiable version of the algorithm. Gradually add pruning conditions one by one, and use brute-force enumeration as an oracle to validate correctness. Performance arguments cannot replace a correctness proof. Stanford’s backtracking course develops this search method through permutations and queen constraints.

Common Issues and Debugging

Symptom	First Check
All results end up the same	Did you copy path when storing the result?
Subsequent branches unexpectedly lack candidates	Did you restore the sets, used, and path after returning?
Duplicate permutations still appear	Was the input sorted first? Are you only skipping duplicates at the same level?
[2, 2] subset disappears	Is the deduplication condition incorrectly written as unconditional skipping of adjacent values?
N-Queens solution misses some configurations	Are separate diagonal checks using row-col and row+col respectively?
Answer count decreases after pruning	Is the pruning condition valid for all remaining candidates?

Observe the Choice Tree

1. Draw the first three layers of unique_permutations([1, 1, 2]), marking the sibling branches that are skipped.
2. Modify the three sets in the N-Queens problem to use boolean arrays, clearly specifying the index translation.
3. Add a fixed-length parameter k to the subset function, on which layer can you terminate early based on the remaining number of elements?
4. Use itertools.permutations and a set to build an oracle for random short inputs.
5. Design a subset sum example involving negative numbers to refute the incorrect pruning heuristic of "stop when current sum exceeds target."

Walk Out of the Choice Tree

The core of backtracking isn't a universal template, but rather making state changes occur in pairs: make a choice, recurse, and undo. Choice trees remain large in most cases; constraints eliminate only branches that have been proven impossible or redundant, and the output size provides an unavoidable lower bound.

If many different paths repeatedly reach the same state, continuing with raw backtracking wastes effort. The next chapter introduces Dynamic Programming, where we learn to define states and reuse solutions to subproblems.