Backtracking

Backtracking is a systematic way to explore all possible solutions by building candidates incrementally and abandoning (“backtracking”) a candidate as soon as it can’t lead to a valid solution.

Why It Matters

Backtracking solves constraint satisfaction problems: N-Queens, Sudoku, permutations, combinations, and subset generation. It’s DFS with pruning — more efficient than brute force because it cuts off invalid branches early.

The Pattern

def backtrack(state, choices):
    if is_solution(state):
        record(state)
        return
    for choice in choices:
        if is_valid(state, choice):
            make(state, choice)       # choose
            backtrack(state, remaining_choices)  # explore
            undo(state, choice)       # un-choose (backtrack)

Code Examples

Generate All Permutations

def permutations(nums: list) -> list[list]:
    result = []
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()  # backtrack
    backtrack([], nums)
    return result
 
assert len(permutations([1,2,3])) == 6
assert [1,2,3] in permutations([1,2,3])

Generate All Subsets

def subsets(nums: list) -> list[list]:
    result = []
    def backtrack(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result
 
assert len(subsets([1,2,3])) == 8  # 2^3 subsets including empty

N-Queens

def solve_n_queens(n: int) -> int:
    """Count solutions to the N-Queens problem."""
    count = 0
    cols = set()
    diag1 = set()  # row - col
    diag2 = set()  # row + col
 
    def backtrack(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: this position is attacked
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            backtrack(row + 1)
            cols.remove(col)        # backtrack
            diag1.remove(row - col)
            diag2.remove(row + col)
 
    backtrack(0)
    return count
 
assert solve_n_queens(4) == 2
assert solve_n_queens(8) == 92

Backtracking vs Brute Force

Backtracking prunes the search tree. For N-Queens:

• Brute force: try all n^n placements
• Backtracking: prune invalid rows/diagonals early, explores far fewer states

When to Use

• “Generate all…” (permutations, combinations, subsets)
• Constraint satisfaction (Sudoku, crossword, N-Queens)
• Path finding with constraints
• Word search in a grid

Related

• Recursion — backtracking is recursive
• BFS and DFS — backtracking is DFS with pruning
• Dynamic Programming — when subproblems overlap, DP is better
• Greedy Algorithms — when local choices are always globally optimal