Backtracking — trying, and un-trying

When a problem means "try every valid combination," backtracking is recursion with one added move — undo a choice and try the next one — which turns an exponential search into something that actually finishes.

Intermediate

4 min read

The shape of problem backtracking solves

def generate_subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(current[:])          # every partial state is a valid subset
        for i in range(start, len(nums)):
            current.append(nums[i])          # choose
            backtrack(i + 1, current)          # explore
            current.pop()                       # un-choose (the "backtrack")
    backtrack(0, [])
    return result
 
generate_subsets([1, 2, 3])
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Backtracking is recursion (from its own lesson) with one specific added pattern: choose, explore, un-choose. At every step, it tries adding one element to the current partial solution, recurses to explore everything that choice leads to, and then explicitly undoes that choice (current.pop()) before trying the next option at the same level. That "un-choose" step — removing the element after fully exploring what it led to — is the entire mechanism the technique is named for: backing out of a choice to go try a different one, from the same starting point.

Why the undo step is the whole point

current.append(nums[i])   # try nums[i]
backtrack(i + 1, current)   # explore everything with nums[i] included
current.pop()               # <-- without this line, every future branch would
                             #     incorrectly still include nums[i]

Without current.pop(), current would keep accumulating every element ever tried across the entire recursive exploration, never reflecting "what's actually chosen at this point in the search" — the next sibling branch (trying nums[i+1] instead of nums[i]) would incorrectly still have nums[i] sitting in current from the previous branch. The undo step is what keeps current an accurate reflection of "the choices made on the path from the root to exactly here," which is required for every branch of the search to explore correctly from a clean, shared starting state.

A more filtered example: combinations that satisfy a constraint

def solve_n_queens_column_conflicts(n):
    solutions = []
    def backtrack(row, columns_used):
        if row == n:
            solutions.append(columns_used[:])
            return
        for col in range(n):
            if col not in columns_used:              # a real constraint check
                columns_used.append(col)
                backtrack(row + 1, columns_used)
                columns_used.pop()
    backtrack(0, [])
    return solutions

This is the same choose/explore/un-choose shape, with one addition: a check (if col not in columns_used) that skips choices known to be invalid before recursing into them at all — this is called pruning, and it's what separates a merely-correct backtracking solution from a genuinely usable one. Without pruning, the search would explore every possible arrangement and only filter out invalid ones at the very end; with pruning, an entire invalid branch (and everything beneath it) is skipped the instant it's known to be invalid, which is often the difference between a search that finishes in milliseconds and one that doesn't finish at all.

Why this is genuinely different from plain recursion

Plain recursion (like tree_sum from the recursion lesson):
  one path down, one answer, no need to undo anything along the way

Backtracking:
  many possible paths, explored one at a time, sharing and reusing
  the same "current partial solution" state across all of them

The recursion lesson's examples (like summing a tree) follow one path down and combine results on the way back up — there's nothing to "undo," because there's no shared mutable state being built up and reused across sibling branches. Backtracking's defining feature is exactly that shared, mutated state (current, columns_used) — building it up through one choice, exploring, then tearing that choice back down before the next sibling branch reuses the same state cleanly.

Why this connects directly to the greedy-vs-DP lesson's theme

The greedy algorithms lesson covered problems where committing to one locally-best choice, without reconsidering it, is either provably fine (activity selection) or silently wrong ([1,3,4] coin denominations). Backtracking is the honest, general-purpose fallback for exactly the problems where greedy can't be trusted and a full dynamic-programming formulation isn't obvious either: instead of proving which choice is always safe, backtracking tries every choice, explores its consequences, and undoes it if it doesn't pan out — genuinely exhaustive, at the real cost of exponential time in the worst case, traded for correctness on problems where no shortcut is known to exist.

The concrete signal backtracking belongs somewhere

"Try every valid combination/arrangement/path, and back out of ones that don't work" — generating all subsets or permutations, solving a maze, placing N queens on a board with no conflicts, solving a Sudoku puzzle — is the tell. If the problem instead has a known greedy or DP shortcut (a provable way to avoid exploring every possibility), reaching for one of those is faster; backtracking is the tool for when no such shortcut is available and exhaustive, prune-as-you-go search is the honest approach.