Backtracking Search

Solving a Sudoku, placing $N$ queens on a board, or finding every valid combination that sums to a target all share the same shape: you make one choice, that choice restricts your future choices, and eventually a bad early choice makes everything downstream impossible. Backtracking is the systematic way to explore that tree of choices: try a candidate, recurse on it, and the moment a partial candidate is proven invalid — not just when it's finished — undo the last choice and try the next one.

The idea: build incrementally, check as you go, undo on failure

A backtracking search is a recursive function with three parts. First, a base case: if the partial solution is already complete, record it (or return it). Second, a loop over the possible next choices at this step. Third, for each choice: apply it, recurse, then undo it before trying the next choice — the "backtrack" that names the technique. The undo step is what lets one array or list represent every partial state along the way, instead of copying state at each recursive call.

The speed of backtracking comes entirely from pruning: checking a constraint as early as possible so an invalid branch is abandoned after one bad choice, not after building out the remaining $k$ choices and discovering the failure at the leaf. In $N$-Queens, checking "does this column or diagonal already have a queen" before placing the next queen — rather than placing all $N$ and checking at the end — is the difference between a search that finishes instantly and one that never finishes for $N$ much above 15.

Worked example: subsets summing to a target

Find all subsets of [2, 3, 5] that sum to 5. Start with an empty partial subset and index 0. At index 0: include 2 (running sum 2, recurse from index 1) or skip it. Including 2, at index 1: include 3 (sum 5 — matches target, record [2,3], stop this branch) or skip 3, include 5 (sum $2+5=7 > 5$ — prune immediately, don't recurse further) or skip 5 (sum stays 2, no subsets left, dead end). Backtrack to index 0's "skip 2" branch: at index 1, include 3 (sum 3) then include 5 (sum $3+5=8>5$, prune) or skip 5 (dead end); skip 3, include 5 alone (sum 5, matches, record [5]). Total answers: [2,3] and [5]. Note the sum-exceeds-target prune fires before recursing one level deeper, not after.

def subsets_summing_to(nums, target):
    results, partial = [], []
    def backtrack(i, remaining):
        if remaining == 0:
            results.append(partial.copy())
            return
        if i == len(nums) or remaining < 0:
            return                          # prune: dead end
        partial.append(nums[i])
        backtrack(i + 1, remaining - nums[i])
        partial.pop()                       # undo — the "backtrack" step
        backtrack(i + 1, remaining)
    backtrack(0, target)
    return results

Where it shows up

Interview staples: N-Queens, Sudoku solver, generate parentheses, combination sum, word search on a grid — all textbook backtracking with problem-specific pruning rules. On a desk, backtracking appears in constraint-satisfaction settings like feasible portfolio construction under discrete lot-size and sector-limit constraints, and in combinatorial search over small discrete parameter grids where early rejection of an infeasible partial configuration saves real compute.