Backtracking

Overview

Backtracking explores a tree of partial solutions, extending a candidate one choice at a time and undoing ("backing out of") choices that violate constraints. It powers combinatorial search such as permutations, subsets, N-Queens, and Sudoku. Worst-case time is exponential, but pruning invalid branches early keeps many practical problems tractable.

Syntax / Usage

The template makes a choice, recurses, then undoes the choice. Pruning conditions cut off branches that cannot lead to a valid solution before descending further.

def permutations(nums):               # O(n * n!) time, O(n) recursion depth
    result, path, used = [], [], [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):    # complete candidate
            result.append(path[:])    # copy the current path
            return
        for i, num in enumerate(nums):
            if used[i]:               # prune: value already chosen
                continue
            used[i] = True; path.append(num)   # make the choice
            backtrack()
            used[i] = False; path.pop()        # undo the choice

    backtrack()
    return result

Examples

Generate all permutations of a list:

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

Solve N-Queens, pruning columns and diagonals under attack:

def solve_n_queens(n):                # counts valid board arrangements
    cols, diag, anti = set(), set(), set()
    def place(row):
        if row == n:
            return 1
        count = 0
        for col in range(n):
            if col in cols or (row - col) in diag or (row + col) in anti:
                continue              # prune: square is attacked
            cols.add(col); diag.add(row - col); anti.add(row + col)
            count += place(row + 1)
            cols.remove(col); diag.remove(row - col); anti.remove(row + col)
        return count
    return place(0)

print(solve_n_queens(8))  # 92

Common Mistakes

• Forgetting to undo a choice, so state leaks into sibling branches.
• Appending path directly instead of a copy, so all results share one mutating list.
• Missing pruning, which turns a feasible search into an intractable full enumeration.
• Mutating shared structures without restoring them exactly, corrupting later paths.
• Confusing backtracking with dynamic programming; backtracking enumerates, DP reuses overlapping results.

See Also

algorithms-recursion algorithms-graph-traversal algorithms-dynamic-programming