Backtracking
Build a solution one choice at a time, and abandon a branch the moment it cannot succeed.
When it applies
Backtracking is exhaustive search with an exit: choose, explore, undo. It fits problems that ask for every solution, the number of solutions, or whether any exists, when the choices are small and discrete: include this element or not, which sign, which column.
The running time is set by how early you can prune. The same search that is hopeless when it builds complete candidates and then checks them becomes practical when it checks each partial candidate and stops as soon as one constraint fails.
Signals: "all subsets", "all permutations", "every way to", "place n pieces so that", "can the set be split". When the count is all you need and states repeat, the next step is memoisation, which turns the search into dynamic programming.
The template
Write this from memory. Every problem in this section is a specialisation of it, and most bugs come from deviating without a reason.
def backtrack(state, choices):
if is_complete(state):
record(state)
return
for c in choices(state):
if not allowed(state, c): # prune: never extend a partial solution that already fails
continue
apply(state, c)
backtrack(state, choices)
undo(state, c) # restore exactly what apply changedvoid backtrack(State& s) {
if (isComplete(s)) { record(s); return; }
for (const auto& c : choices(s)) {
if (!allowed(s, c)) continue; // prune early
apply(s, c);
backtrack(s);
undo(s, c); // restore exactly what apply changed
}
}void backtrack(State s) {
if (isComplete(s)) { record(s); return; }
for (Choice c : choices(s)) {
if (!allowed(s, c)) continue; // prune early
apply(s, c);
backtrack(s);
undo(s, c); // restore exactly what apply changed
}
}function backtrack(state) {
if (isComplete(state)) { record(state); return; }
for (const c of choices(state)) {
if (!allowed(state, c)) continue; // prune early
apply(state, c);
backtrack(state);
undo(state, c); // restore exactly what apply changed
}
}fn backtrack(s: &mut State, out: &mut Vec<Solution>) {
if s.is_complete() { out.push(s.snapshot()); return; }
for c in s.choices() {
if !s.allowed(&c) { continue; } // prune early
s.apply(&c);
backtrack(s, out);
s.undo(&c); // restore exactly what apply changed
}
}-- In Haskell the "undo" is free: each branch gets its own immutable state.
search :: State -> [Solution]
search s
| complete s = [finish s]
| otherwise = concat [ search (apply c s) | c <- choices s, allowed s c ]Problems
Sum of every subset’s XOR
Every element is either in or out. Walking that binary tree visits each subset once, carrying its XOR as you go.
Open the problem → Medium20 minSigns that reach a target
Put + or − in front of each number and count the ways to hit the target. Search first, then notice the states repeat.
Open the problem → Hard25 minCounting n-queens placements
Place one queen per row, and never place one where it is already attacked. Bitmasks make the check a single AND.
Open the problem →Or sit a timed interview: a fixed window, limited submissions, and a report at the end.