Backtracking Patterns: Subsets, Permutations, N-Queens

Backtracking is the algorithmic shape of “try every possibility, but abandon any path that cannot lead to a valid answer.” It is depth-first search over a decision tree, augmented with pruning. Once you internalize the template, an entire family of problems, subsets, permutations, combinations, N-Queens, Sudoku, word search, palindrome partitioning, collapses into the same three steps.

The template

Every backtracking algorithm has the same skeleton:

def backtrack(state):
    if is_solution(state):
        record(state)
        return
    for choice in candidates(state):
        if not is_valid(choice, state):
            continue
        apply(choice, state)
        backtrack(state)
        undo(choice, state)

The three load-bearing pieces are:

1. Choose a candidate and apply it to the current partial state.
2. Explore recursively from the new state.
3. Un-choose by undoing the change so the next iteration starts clean.

The “un-choose” step is what makes this backtracking rather than plain recursion. It lets you reuse a single mutable state object instead of copying, which is the difference between an elegant solution and a slow one.

Pruning is the whole game

Naive enumeration is O(b^d) where b is the branching factor and d is the depth. That blows up fast. Pruning means cutting branches early by checking constraints before recursing. The earlier you prune, the smaller the search tree.

Two pruning patterns are universal:

• Constraint checks. If the candidate violates a rule (a duplicate, a conflict, an upper bound), skip it.
• Bound checks. If the best result reachable from this state cannot beat the current best, skip it. This is “branch and bound” territory.

Problem 1: Generate all subsets

Given a set of distinct integers, return all possible subsets.

There are 2^n subsets. The decision tree branches twice at each index: include the element or skip it.

def subsets(nums):
    res = []
    path = []

    def backtrack(i):
        if i == len(nums):
            res.append(path.copy())
            return
        # exclude nums[i]
        backtrack(i + 1)
        # include nums[i]
        path.append(nums[i])
        backtrack(i + 1)
        path.pop()

    backtrack(0)
    return res

Time is O(n * 2^n) because we generate 2^n subsets and copy each into the output. Space, excluding output, is O(n) for the recursion stack.

The same template generates combinations (subsets of fixed size) by adding if len(path) == k: as the base case, and permutations by iterating over remaining elements and marking each as used.

Problem 2: Permutations

Given a list of distinct integers, return all permutations.

def permute(nums):
    res = []
    used = [False] * len(nums)
    path = []

    def backtrack():
        if len(path) == len(nums):
            res.append(path.copy())
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return res

There are n! permutations, each of length n, so the runtime is O(n * n!). This is unavoidable for the enumeration itself.

For permutations with duplicates, sort the input first and skip a candidate if it is identical to its previous sibling and that sibling is not currently used. This avoids generating the same arrangement twice.

Problem 3: N-Queens

Place n queens on an n x n board so that none attack each other.

Place one queen per row. For each row, try every column; mark the column, the two diagonals as attacked, recurse, then unmark.

def solve_n_queens(n):
    cols = set()
    diag1 = set()  # r - c
    diag2 = set()  # r + c
    board = [['.'] * n for _ in range(n)]
    res = []

    def backtrack(r):
        if r == n:
            res.append([''.join(row) for row in board])
            return
        for c in range(n):
            if c in cols or (r - c) in diag1 or (r + c) in diag2:
                continue
            cols.add(c); diag1.add(r - c); diag2.add(r + c)
            board[r][c] = 'Q'
            backtrack(r + 1)
            board[r][c] = '.'
            cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)

    backtrack(0)
    return res

The naive bound is n^n, but the three sets prune so aggressively that the practical runtime for n = 12 finishes in milliseconds. This is the clearest demonstration that pruning, not theoretical complexity, governs real-world performance.

Complexity, honestly

Backtracking complexities look scary because they often are. But the useful framing is:

• Output-sensitive bounds. If a problem has K solutions, you cannot do better than O(K * cost_per_solution).
• Worst case vs. typical case. Sudoku is exponential in the worst case, but real puzzles run in microseconds because constraints prune most branches near the root.
• Memoization is not backtracking. If overlapping subproblems exist, switch to dynamic programming; see Dynamic Programming Introduction. Backtracking shines exactly when subproblems are not shared.

Patterns to recognize

• “Return all” problems are almost always backtracking: all subsets, all permutations, all paths, all valid expressions.
• “Count” problems sometimes turn into DP because counting does not need to enumerate.
• “Find one” problems are backtracking with early return on the first success.
• Constraints stated as “no two of X” or “must satisfy Y” are signals to add pruning sets like the ones in N-Queens.

Common pitfalls

• Forgetting to undo. A missing pop or unmarking step silently corrupts state and produces wrong answers.
• Appending the live path instead of path.copy(). The reference will be mutated by later steps.
• Wrong base case. Make sure the recursion terminates at the right depth before reading the partial state as a solution.
• Skipping pruning. Without constraint checks, even small inputs become impossibly slow.

Wrap up

Backtracking is one template applied with discipline: choose, explore, un-choose, prune. Subsets, permutations, combinations, N-Queens, Sudoku, and word search all collapse into that pattern with a different is_valid and a different base case. Practice writing the template from memory, then focus your effort on the pruning, because pruning is where the algorithm becomes practical.