Backtracking
Choose, explore, undo
Recursion that builds something up and takes it apart again. The undo is the whole difference.
Key idea
What backtracking is
Backtracking explores a tree of decisions. At each step you have a set of choices, you take one, you recurse to make the remaining decisions, and then you put things back the way they were and try the next choice.
That last part is what makes it backtracking rather than plain recursion. The state being built is shared across the whole search, so anything a branch changes has to be unchanged before its sibling runs.
Why it works
The invariant the undo protects
State the rule as: when explore returns, current holds exactly what it held when explore was called.
Every recursive call relies on that. If a branch leaves an extra element behind, its sibling starts from a corrupted state and every result after that point is wrong. The pop is what keeps the promise.
Check it by pairing: every append has exactly one matching pop, on every path out of the function including early returns.
Gotcha
Append a copy, not the list itself
results.append(current) stores a reference to the same list that the search keeps mutating. By the time the search finishes, every stored result points at the same, now empty, list.
Store current[:] or list(current) or "".join(current). Anything that takes a snapshot. This is the single most common backtracking bug and its symptom is distinctive: the right number of results, all identical, usually all empty.
Key idea
The decision tree
It helps to picture what is being searched. Each level of the recursion is one decision, and each loop iteration is one branch out of the current node.
The number of leaves is the number of results, and the depth is how many decisions each result requires. Those two numbers give you the complexity directly, which is why sketching the tree for a tiny input is the fastest way to work out what a backtracking solution costs.
Key idea
A second framing: include or exclude
Some problems are more naturally written as a binary decision per element rather than a loop over choices. Take this element or do not, then move to the next.
Both framings generate the same things and one is usually shorter for a given problem. Being able to switch between them is worth practicing, because a problem that looks awkward in one is often obvious in the other.
Below, each element is either taken or not, and what accumulates is a single number rather than a list. That removes the need for an undo at all: the state travels as a parameter, so nothing has to be put back.
Tip
Carrying state as a parameter instead of undoing it
Passing the accumulated value down as an argument works whenever that value is cheap to copy, which numbers, strings, and small tuples all are. Each call gets its own copy, so nothing is shared and nothing needs restoring.
The append-and-pop pair comes back as soon as the accumulated state is a list, because copying a list at every node would turn a linear amount of work per path into a quadratic one. Choose by asking what the state costs to copy, not by preference.
Cost
What these cost
There are 2 to the n subsets of n items and n factorial orderings, and no algorithm can produce them faster than it can print them. So the lower bound is the size of the output.
Quote the cost as the number of results times the work per result. For subsets that is O(n times 2 to the n), because copying each subset costs up to n. Saying just 2 to the n undercounts, and interviewers notice.
Predict the output: forgetting the undo
The pop is missing. The base case uses >= rather than ==, which is the only reason this terminates at all. Type what it prints.
Template drills
Three searches on the same skeleton. all_paths lists every path from the top-left to the bottom-right of a grid moving only right or down, as strings of R and D. combinations_of lists every way to choose exactly k items from a list, keeping the original order. all_splits lists every way to break a string into non-empty consecutive pieces.
Tests
print(sorted(all_paths(2, 2)))
print(sorted(all_paths(1, 3)))
print(sorted(combinations_of([1, 2, 3], 2)))
print(sorted(combinations_of([1, 2], 0)))
print(len(all_splits("abc")), sorted(all_splits("ab")))Output
Run the tests when you are ready.
Subsets
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.