Backtracking

The core idea

Backtracking is recursion that explores choices and undoes them. You stand at a state, list the choices available, take one, recurse, then unmake the choice and try the next. The shape is identical across every backtracking problem; only the choice set and the constraint change.

The skeleton:

def backtrack(state):
    if is_solution(state):
        record(state)
        return
    for choice in choices(state):
        if prune(state, choice):
            continue
        apply(state, choice)
        backtrack(state)
        undo(state, choice)

That is the entire pattern. Read it twice.

Backtracking is the right answer when the problem asks for all valid configurations (enumerate), or the count of valid configurations, or the best of them when no greedy or DP simplification works.

When to reach for it

Trigger phrases:

• "generate all ..."
• "list every permutation / combination / subset"
• "place k items such that ..." (n-queens, sudoku)
• "find a path through a maze"
• the answer space is exponential and there is no polynomial reduction

How to approach

1. Decide what state is. Usually a partial answer (a list being built up).
2. Decide what choices(state) are at each step. The fewer the better: prune as early as possible.
3. Write the base case: when is state a solution?
4. Write prune: which choices are guaranteed to fail? Pruning is what separates O(n!) from O(2^n) from "fast enough".
5. Apply and undo must be symmetric. If you append, you pop. If you mark used, you unmark.

Real-world applications

• Constraint solvers: scheduling exams without clashes, room assignment.
• Configuration generators: every valid build flag combination.
• Compilers: pattern matching against a rule set with overlap.
• Game solvers: chess engines, sudoku, n-queens.
• Test generators: enumerate small inputs to fuzz.
• Auto-completion when constraints are non-trivial.

In the AI-integrated workspace

The first failure mode: an agent forgetting the undo step. The recursion mutates a shared list, the parent call sees the mutation, and the resulting bug looks like "permutations include too many elements". Any backtracking review asks: "Does every apply have a paired undo?".

The second failure mode: missing the prune. The agent produces correct but exponential code that times out on n=10. The cue in code review is the absence of any conditional after the loop's choice; a real backtracker prunes.

The third, subtle: recording the solution by reference, not by copy. Python and most languages share the list across recursive calls; record(state) must record(list(state)). Generated code routinely gets this wrong and then "passes the tests with a single output and fails on multi-output".

In an agentic workflow, backtracking is one of the places where the human still has to prove correctness by induction, because the agent will not verify the recursion handles every case. Spell out the invariant: "after backtrack(state) returns, state is exactly what it was before the call".

Problems in this cluster

Medium only: letter-combinations-phone, subsets, permutations, combination-sum.

Start with letter-combinations-phone. The choice set is small (3 or 4 letters per digit) and the base case is obvious, so the pure backtracking shape is easy to see.