← Backtracking · guided lesson
Backtracking
the story
Backtracking (choose → explore → un-choose)
Every tool here exists because something was too slow or broke without it. Here is what.
Who named it is disputed. Golomb and Baumert (1965) say the mathematician D. H. Lehmer named it "backtrack"; Knuth (1975) credits R. J. Walker, who "aptly called" it backtracking. In 1960 Walker published a short note describing it as a general method for combinatorial problems. As Knuth tells it, Walker's 1950s n-queens program already kept the attacked columns and diagonals as bit vectors. In 1965 Golomb and Baumert's "Backtrack Programming" (Journal of the ACM) set the method out with many examples — and, Knuth notes, already suggested branching first on the choice with the fewest options left.
the problem it solved
Searching enormous spaces of combinations on early computers without building every complete candidate first.
why it matters: without it
Every "find all" or "place under rules" problem would mean building every complete candidate and checking it at the end — billions of boards instead of two thousand calls.
sources: Golomb & Baumert — Backtrack Programming (Journal of the ACM 12(4), 1965) ↗ · Walker — An enumerative technique for a class of combinatorial problems (Proc. Symp. Applied Math. 10, AMS, 1960) ↗ · Knuth — The Art of Computer Programming, §7.2.2 Backtrack programming (pre-fascicle 5B) ↗ · Knuth — Estimating the efficiency of backtrack programs (Mathematics of Computation 29, 1975): "which R. J. Walker has aptly called backtracking" ↗ · NIST Dictionary of Algorithms and Data Structures — backtracking (quotes Golomb & Baumert) ↗
also in this chapter: Subsets & combinations (the start index) · Generating permutations · Constraint pruning (N-Queens, Sudoku)
the idea
The idea in 30 seconds
Build an answer one choice at a time. After each choice, recurse to make the next one.
When a branch is finished (or hopeless), undo the last choice and try the next option. That undo is the "back" in backtracking.
It is DFS over a decision tree you never build in memory — and pruning cuts whole subtrees you can prove are useless.
picture this
Solving a Sudoku in a phone app: pencil in a digit and move to the next cell. The moment a row breaks, tap Undo back to your last guess and try its next digit. You never look at every possible grid — Undo plus "this already breaks a rule" does all the work.
watch it
The template — choose k of n
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
The template — choose k of n
Choose → explore → un-choose, one number at a time, always in increasing order. Red ✗ branches are cut by the loop bound before any call is made.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Subsets — watch the decision tree grow
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Subsets — watch the decision tree grow
Each node is one subset. The path stack grows on *choose* and shrinks on *un-choose*. Magenta = where we are, violet = the current path, green = recorded.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 8
Read it once. Say it out loud once. Bas.
The template: if (goal) record; for each choice: choose → recurse → un-choose. Almost every backtracking problem is this loop with a different goal, choice list and pruning rule.
key idea 2 of 8
Read it once. Say it out loud once. Bas.
State must be restored exactly. Whatever you change before the recursive call (path, used[], board cell) you undo right after it. Forget one piece and later branches see garbage.
key idea 3 of 8
Read it once. Say it out loud once. Bas.
Record a copy. result.add(new ArrayList<>(path)) — adding path itself stores a reference that you will empty later.
key idea 4 of 8
Read it once. Say it out loud once. Bas.
Three shapes: subsets (each element in or out → 2ⁿ), combinations (choose from start onward so order doesn't matter), permutations (choose any unused element → n!).
key idea 5 of 8
Read it once. Say it out loud once. Bas.
Duplicates: sort first, then at the same depth skip a value equal to its left neighbour: if (i > start && a[i] == a[i-1]) continue;.
key idea 6 of 8
Read it once. Say it out loud once. Bas.
Pruning is where the speed comes from: sort and break when a value overshoots, track counts (open/close brackets), or use O(1) attack tables (N-Queens).
key idea 7 of 8
Read it once. Say it out loud once. Bas.
Complexity = (number of nodes) × (work per node). Typical results: O(n·2ⁿ) subsets, O(n·n!) permutations, O(b^d) for branching b and depth d.
key idea 8 of 8
Read it once. Say it out loud once. Bas.
Backtracking is only fast enough for small inputs (n ≲ 20 for 2ⁿ, n ≲ 10 for n!). If n is large, look for DP or greedy instead.
spot the pattern
When you see this, think this
"Return all …" (subsets, permutations, combinations, partitions, valid strings)
Backtracking — the output itself is exponential, so nothing faster exists
Small constraints: n ≤ 10, 15, 20, a 9×9 board, words ≤ 15 letters
An exponential search is allowed; plan choose / explore / un-choose
"Place" items under constraints (queens, Sudoku digits, colours)
Backtracking with O(1) constraint tables for pruning
Find a path through a grid that spells / sums to something, cells used once
DFS + mark cell + restore (grid backtracking)
+2 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
result.add(path)instead ofresult.add(new ArrayList<>(path))— every stored answer ends up as the same (empty) list.- Forgetting to undo one piece of state (e.g. resetting
used[i]but not poppingpath, or not restoring a board cell).
quick check
One question. No pressure.
Why does result.add(path) produce a list of empty lists at the end?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Subsets
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Why record new ArrayList<>(path) and not path itself?
Question 1: Why record new ArrayList<>(path) and not path itself?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.