Backtracking: prune before you generate

Backtracking is exhaustive search with an undo. Written naively it explores everything and times out; written with pruning it explores a small fraction of the same tree and finishes instantly. The algorithm is identical — only the order and the early exits change.

The skeleton

The undo is what makes it backtracking rather than plain recursion, and it is where the bugs live. Every mutation on the way down needs an exact inverse on the way up — including the ones you forgot were mutations.

Generate-and-filter versus prune

The naive N-Queens generates every arrangement and checks validity at the leaves: n! leaves for n queens. Checking validity as you place each queen cuts entire subtrees at the moment they become impossible. For n = 8 that is the difference between 40,320 complete arrangements examined and about 2,000 partial states visited.

Handling duplicates

Generating subsets or permutations of an input with repeated values produces duplicate outputs unless you suppress them. Sort first, then skip a choice when it equals the previous one and the previous one was not used at this level.

Deduplicating the output afterwards with a set gives the same answers and does the same wasted work. The point of the skip is that the duplicate branch is never walked.

Ordering choices matters

For constraint problems, trying the most constrained option first tends to cut the tree fastest — this is the standard heuristic in Sudoku solvers, where filling the cell with fewest candidates first turns an intractable search into an instant one. The choices are the same; the order changes how quickly contradictions surface.

When to stop optimising

Backtracking is exponential and pruning changes the base, not the exponent. If n is 20 and the search is 2^n, pruning may well be enough. If n is 200, no pruning will save it and the problem wants dynamic programming or a greedy argument instead. Read the constraint line before deciding backtracking is the answer.