Backtracking
How do you enumerate every option without missing or repeating one?
Thirteen rows for five answers
A promotion lets customers stack vouchers, and the fraud team wants every way to reach exactly ₹500 with vouchers of ₹100, ₹200 and ₹300, so carts that game the offer can be spotted. The obvious recursion is short: at each step try every voucher that still fits, and recurse on what is left. It prints 13 rows. Count the different combinations by hand and you get five. The other eight are the same vouchers in another order: 100, 200, 200, then 200, 100, 200, then 200, 200, 100.
The quick fix is a set: sort each row and keep the unique ones. On this input it works. Now the real offer: seven voucher values from ₹50 to ₹500 and a target of ₹2,000. There are 5,216 combinations. Work out roughly how many ordered rows that means before reading on. The recursion would build about 420 billion of them and throw away all but 5,216. A set at the end is too late. The repeats have to be impossible to build in the first place, which means one rule about what the next voucher may be.
Pause and predict Which rule on the next voucher makes each combination come out exactly once?
A tree of choices, walked one path at a time
When a problem asks for every subset, every arrangement or every valid board, the answer itself has exponential size, so no trick can avoid listing it. The job is to list each answer exactly once, and to waste as little work as possible on the way.
Build each answer one choice at a time. The choices form a tree: the root is the empty answer, each edge is one choice, and each node is the partial answer spelled by the edges above it. That is the recursion tree, and backtracking walks it depth first.
It never stores the tree. It keeps one list, path, holding the partial answer at the node it is currently on. Going down an edge appends a choice to path, and coming back up removes it. The three steps are called choose, recurse and unchoose.
The cost is the size of the tree times the work per node. Listing the subsets of n elements visits 2ⁿ nodes, and listing the orderings reaches about n! leaves. That is why these problems keep n below about 15 or 20.
The recursive call decides what "different" means
Pause and predict Permutations of [1, 2, 3] must list all six orders. Does a loop with a start index still work?
With a start index, [2, 3] and [3, 2] count as one answer, because only one of them is increasing. Permutations need both, so they drop the start index and record which values are already taken in an array used[]. Combination Sum allows a value to repeat but not to be reordered, so it recurses with i: the same index again, never a smaller one. That is the voucher rule from the opening.
Duplicates: sort, then skip at the same depth
With [2, 1, 2], picking the first 2 or the second 2 gives the same subset. First sort, so that equal values sit next to each other: [1, 2, 2]. Then look at one loop, which chooses the next value of the path. If the loop tries the second 2 after the first, it builds only subsets that the first 2 already built, because the first 2 has the same value and has every later element available too.
Pause and predict On [1, 2, 2], the code skips a value with the test i > 0 && a[i] == a[i - 1]. How many subsets come out?
Record a copy
path is one list, changed by every choose and unchoose. Adding path itself to the answers adds a reference to that one list, so at the end every answer is the same list, which is empty. Add a copy instead, new ArrayList<>(path) in Java or path[:] in Python, so each answer keeps the contents path had at that node.
Pruning
To prune is to refuse a choice that cannot lead to an answer, which cuts off its whole subtree. Every prune needs a reason it is safe. In Combination Sum the candidates are sorted, so once one is bigger than the amount that remains, every later one is too. So break out of the loop; a continue would test each of the later candidates for nothing. In N-Queens a square that is already attacked can never be part of a valid board, so it is never tried.
On a grid: mark, then unmark
In Word Search the path is a chain of neighbouring cells, and a cell is marked as used by writing # on the board. The mark means "on the current path", so it has to be removed when the call returns. A cell that a failed path passed through must be free again for the next path.
How to recognise it
The word to listen for is "all": all subsets, all orderings, all boards, every way to split a string. The size of the input confirms it: when the output is exponential in size, the input must be small.
Pause and predict n is 200, and the question asks how many subsets sum to 1,000. Should you use backtracking?
Four that only look like it
- Counting the ways, or finding the best one, with n in the hundreds: only a number is wanted, and many paths reach the same state. That is dynamic programming, or knapsack for subset sums.
- A tree given in the input, where each node returns a value to its parent: that is trees. Backtracking walks a tree of choices that exists only in the recursion, and passes the path down.
- Visiting every cell once, as in counting islands: the visited mark never comes off. That is graph search. Backtracking removes its marks because one cell can lie on many different paths.
- Searching for many words in one grid: still backtracking, but the walk follows a trie, so one walk checks every word at once.
Where it bites
Pause and predict In Java, path is [1, 0] and int v = 0. After path.remove(v), what is path?
- Recording the path by reference. Every answer then refers to the same list, which is empty at the end. Record a copy.
- The wrong reuse rule. Recurse with
i + 1when each element may be used once, withiwhen it may be reused, and never with0in a combination problem. i > 0instead ofi > startin the duplicate skip, or forgetting to sort first.- Undoing only part of a choice. Unchoose everything the choose did: both the path and
used[i]in permutations, all three sets in N-Queens, and the mark on the board in Word Search. - Using
continuewherebreakis safe, on sorted input, orbreakwhere it is not safe, on unsorted input.