Backtracking — choose, recurse, unchoose

Subsets, permutations, combinations, N-queens, sudoku. All variations of one template. Pruning is what makes it tractable.

The on-ramp: try a choice, recurse, undo it

Strip backtracking down to its bones and it is just three verbs in a loop: try a choice, recurse to see where it leads, then undo it and try the next choice. Nothing more. The word backtracking literally describes that "undo" step — when a branch is finished (or fails), you track back up to the last decision point and explore the alternative you haven't tried yet. It is depth-first exploration of a tree of decisions, with a tidy-up after every branch so the next branch is unpolluted.

It helps to name the pieces precisely:

• State — the partial answer you've built so far (above, the path list). It is incomplete and constantly mutating.
• Choice — one move that extends the state (append a number, place a queen, write a digit into a sudoku cell).
• Choose — apply the move to the state. Unchoose — reverse exactly that move, restoring the state to what it was before. Choose and unchoose must be perfect mirrors; if they don't cancel out, later branches inherit garbage.
• Goal / leaf — a state that is complete (a full subset, a placed board). When you reach one, you record it (the snapshot) and return.
• Dead end — a state that can no longer become a valid answer. You stop and back up immediately (this is where pruning lives).

The decision tree and the state space

Every backtracking problem has an invisible decision tree: a branching diagram where each node is a partial state and each edge is one choice. The root is the empty state; the leaves are complete answers. The full set of every state reachable this way — every node in that tree — is called the state space. Backtracking is nothing but a depth-first walk over this tree: go all the way down one branch, record the leaf, then climb back up (that's the unchoose) and walk down the next branch.

For the [1,2] subsets above, the tree has a yes/no fork at each level. Read top-to-bottom, here is the exact tree the trace walked, with the leaf each path reaches:

# decision tree for subsets of [1, 2]   (L = "take" branch, R = "skip" branch)
#                         bt(0) path=[]
#                 take 1 /            \ skip 1
#            bt(1) path=[1]        bt(1) path=[]
#      take 2 /     \ skip 2     take 2 /     \ skip 2
#   bt(2) [1,2]   bt(2) [1]   bt(2) [2]    bt(2) []
#   leaf -> [1,2] leaf -> [1] leaf -> [2]  leaf -> []

The four leaves, left to right, are the four subsets — and they come out in exactly the order Step 3 / Step 4 / Step 6 / Step 6 produced them. Drawing this tree on scratch paper is the single most useful habit for any backtracking question: once you can see the tree, the code writes itself.

The general template

Almost every backtracking solution is the same skeleton with three blanks filled in: when is the state a complete answer, what choices are available now, and how do I choose / unchoose. Memorise this shape and you can adapt it to any of the variants below.

def backtrack(state):
    if is_complete(state):       # reached a goal / leaf?
        record(state[:])           # SNAPSHOT a copy, then stop
        return
    for choice in candidates(state):
        if not is_valid(state, choice):  # PRUNE dead ends early
            continue
        apply(state, choice)        # choose
        backtrack(state)            # explore (recurse)
        undo(state, choice)         # unchoose — MUST mirror apply()

The subsets code below is this template with is_complete = "ran out of indices", and the two-way (take / skip) fork written out explicitly instead of as a loop. Both styles are correct; the loop style generalises more cleanly to problems where each step has many candidates rather than just two.

def subsets(nums):
    res, path = [], []
    def bt(i):
        if i == len(nums):
            res.append(path[:])         # snapshot
            return
        path.append(nums[i])            # choose
        bt(i + 1)
        path.pop()                      # unchoose
        bt(i + 1)
    bt(0)
    return res

Subsets vs permutations vs combinations

These three words name the three problems you'll meet most, and people mix them up constantly. They differ on two questions: does order matter? and how many items do I pick?

• Subsets — every "in or out" selection of any size; order doesn't matter. From [1,2,3] you get all 2³ = 8 of them, including []. Fork take/skip at each index (the code above).
• Combinations — like subsets but you fix the size: "choose k of n, order doesn't matter." combinations([1,2,3], 2) gives [1,2], [1,3], [2,3] — there are C(n,k) of them. Same template, but you only snapshot when len(path) == k, and you recurse from i+1 so you never reuse or reorder an element.
• Permutations — every ordering of all the items; order does matter, so [1,2] and [2,1] are different answers. There are n! of them. Instead of an index you loop over every unused element at each level and mark it used (then unmark on the way back).

Here is the permutation variant, so you can see how "loop over unused candidates" replaces the take/skip fork:

def permute(nums):
    res, path = [], []
    used = [False] * len(nums)
    def bt():
        if len(path) == len(nums):
            res.append(path[:])         # snapshot a full ordering
            return
        for j in range(len(nums)):
            if used[j]:
                continue                  # prune: can't reuse an element
            used[j] = True; path.append(nums[j])   # choose
            bt()
            path.pop(); used[j] = False          # unchoose (mirror!)
    bt()
    return res

Notice the unchoose line undoes both mutations from the choose line, in reverse. That mirroring is the discipline that keeps backtracking correct.

Pruning and constraint satisfaction

Pruning is cutting off a branch the moment you can prove it cannot reach a valid answer — instead of recursing into a doomed subtree and discovering the failure at the bottom. In the permutation code, if used[j]: continue is a tiny prune. In a constraint satisfaction problem — one defined by rules every complete answer must obey, like N-queens (no two queens attack) or sudoku (no repeated digit in a row, column, or box) — pruning is the whole game. You check each rule before recursing; if placing this queen already violates a constraint, you skip it and never explore the millions of arrangements beneath it.

The intuition for why pruning matters so much: the state space is a tree whose size is exponential. A prune near the top of the tree deletes an entire exponential subtree in one stroke. Cutting one branch at depth 1 of an N-queens board can save you from exploring N!-worth of arrangements below it. That is why a brute-force "generate every arrangement, then filter" approach is hopeless while a pruned backtracker solves the same board instantly — same tree, but you never walk the dead parts.

Complexity intuition

Backtracking is exponential by nature, because the number of leaves in the decision tree grows multiplicatively: each level multiplies the count of paths by the number of choices there. Subsets give 2ⁿ (two choices, take/skip, at each of n levels); permutations give n! (n choices, then n−1, then n−2…). Add the per-leaf snapshot cost (up to n) and you get n·2ⁿ for subsets, n·n! for permutations. There is no way around producing exponentially many answers when the output is exponentially large — that work is inherent, not a flaw in your code.

Where you have real leverage is the decision problems: "does any valid arrangement exist?" Here pruning is decisive. Worst-case Big-O is still exponential (a pathological input could force you to explore everything), but for typical inputs an aggressive prune turns an astronomically large tree into a tiny walked portion. The honest interview answer: state the exponential worst case, then add "but constraint checks prune most of the tree in practice, so it finishes fast on real inputs."

Recognition signals and pitfalls

Reach for backtracking when the problem asks you to enumerate or find arrangements built from a sequence of choices. Telltale phrasings:

• "Generate all / list every…" subsets, permutations, combinations, partitions, valid expressions.
• "Find a / count the / does there exist a…" arrangement satisfying constraints (N-queens, sudoku, word search on a grid, graph coloring).
• The answer is built incrementally and a partial answer can be checked for validity or abandoned.
• Brute force is "try all combinations," and n is small (often ≤ 20) — a hint that exponential is acceptable.

The pitfalls that actually fail interviews:

Generate all subsets — the choose / recurse / unchoose rhythm: