Backtracking

The idea, with zero jargon

You're in a maze. At every junction you pick a corridor and walk. Hit a dead end? You walk back to the junction and take the next corridor. You never teleport, you never clone yourself — one walker, exploring everything, by remembering to undo.

That's the entire algorithm:

1. Choose — pick one of the available options.
2. Explore — go deeper with that choice made.
3. Un-choose — undo the choice, so the next option starts from a clean slate.

The un-choose step is what beginners forget, and it's the whole trick: it's what lets the same path/board/array be reused for every branch instead of copying it at every step.

Watch it run: N-Queens

The classic constraint puzzle: place queens so none can attack another. Watch three things — choices being made (green), illegal squares being rejected before going deeper (red ✕), and the backtrack itself: a queen being lifted off the board when everything below it failed.

Watch it run: subsets

Most backtracking interview problems are secretly this: walk the items left to right, and for each one make a yes/no decision. Every route through the decisions produces one subset.

The template

Build a candidate incrementally; at each step choose an option, explore deeper, then un-choose (undo) to try the next. It's DFS over the space of partial solutions — the "graph" is imaginary: nodes are partial answers, edges are choices.

def subsets(nums):
    res, path = [], []
    def backtrack(start):
        res.append(path[:])              # every node is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])         # choose
            backtrack(i + 1)             # explore (i+1 ⇒ no reuse, no dupes)
            path.pop()                   # un-choose
    backtrack(0)
    return res

The start index is what prevents duplicate subsets; for permutations you'd instead track a used[] set and iterate all indices.

Knowing the shape

How to recognize a backtracking problem

The wording gives it away. Reach for backtracking when the problem says:

• "all subsets / all permutations / all combinations / every way to…" → you're asked to enumerate, not to find one best answer.
• "place / arrange / assign … such that no two conflict" → constraint puzzle (N-Queens, Sudoku, graph coloring).
• "can you split / partition the input into groups that…" → try assignments, undo on failure.
• The input is tiny (n ≤ ~15). Exponential is expected; the question is whether your recursion is clean and your pruning is real.

If instead it asks for the count of ways or the best value — and the same sub-questions repeat — that's dynamic programming: DP remembers answers, backtracking enumerates paths.

Pruning is the whole point

Naive enumeration is O(2ⁿ) or O(n!). Pruning — cutting branches that can't lead to a valid/better solution — is what makes it pass. You saw it in the N-Queens player: the red ✕ squares were rejected before recursing, killing whole subtrees of doomed arrangements in one comparison. Sort to enable early termination, skip equal siblings to dedupe, and check constraints before recursing.

Think one through

Practice — climb the ladder

Every backtracking solution is the same skeleton: choose → explore → un-choose. The only things that change are the choice list and the pruning.