For a long stretch, backtracking was the topic I quietly dreaded. The recursion was easy enough to write. The code ran. It even returned answers. They were just wrong, and not in a way that threw an error you could chase. A Combination Sum solution would spit out duplicate-looking results with no obvious culprit line. The fix, when it came, had nothing to do with understanding recursion better. It was one habit that kept getting skipped.
Here's what changed once backtracking stopped being a clever trick and became a fixed loop.
What changed
- Backtracking is a depth first walk over a state space tree, and the tree is the part worth drawing first.
- The loop is always the same: choose an option, check the constraint, undo the choice on the way back up.
- The undo step is the easiest to drop, and dropping it silently corrupts later branches.
- Pruning before you recurse, not after you reach a leaf, is where the speed lives.
- Once the same partial state repeats across branches, the whole thing becomes top down DP.
Where my backtracking kept breaking
The mistake was always the same, and naming it took embarrassingly long. You build a partial solution by mutating a shared list, recurse, then move on to the next option without ever putting the list back the way you found it. So branch two starts with branch one's leftovers still inside it.
What broke wasn't the recursion. It was that the path never got restored on the way back up.
The reason it's so hard to catch: nothing crashes. A forgotten undo doesn't raise an exception. It quietly hands stale state to the next branch, and the answers look plausible until you check them by hand. That single omission costs more debugging time than any actual algorithmic concept.
Picture it concretely on a small Combination Sum case, candidates [2, 3] and target 5. The first branch explores [2, 2, ...], overshoots, and returns. If that branch left a stray 2 in the shared list, the next branch starts from [2] when it should start from []. Now the [3, ...] branch is really exploring [2, 3, ...], and the result set fills with combinations that were never asked for. Reading the function top to bottom, every line looks reasonable. The bug only shows up when you trace the shared list across two sibling branches and notice it isn't the same length going in as coming out.
What I started doing differently
The shift was to stop writing backtracking freehand and write the same three line frame every time, then fill it in. Choose, check, undo, in that order, with the undo non negotiable. Here's the before and after, once it became a fixed habit:
| Then | Now |
|---|
| Recursion written ad hoc, undo when remembered | Choose, check, undo written as a fixed frame first |
| Constraints checked at the leaf | Constraint checked before recursing, so dead branches die early |
| Debugged by re-reading the whole function | Trace one branch, confirm state is restored after the call |
| Each problem treated as new | Slot the problem into one of three known shapes |
The "check before recurse" row mattered more than expected. Pruning at the leaf still gives correct answers, it's just slow, and on a tight time limit slow is the same as failing.
What that looked like on Combination Sum
Combination Sum is the problem that finally made it click for me. Given a list of candidates and a target, find every combination that sums to the target, where a number can be reused. It's a conditional enumeration problem, so you prune any branch whose running sum overshoots.
Here's the frame, filled in:
def combination_sum(candidates, target):
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:]) # finished combination
return
if remaining < 0:
return # overshot, prune this branch
for i in range(start, len(candidates)):
path.append(candidates[i]) # choose
backtrack(i, path, remaining - candidates[i]) # explore (reuse allowed)
path.pop() # undo
backtrack(0, [], target)
return result
The line that used to go missing is path.pop(). Without it, every combination after the first carries elements from the previous one. The path[:] matters too, it copies the list into the result instead of storing a reference that later pop calls would mutate out from under you. Two small lines, and they're the entire difference between a function that works and one that lies to you.
The start index is the other quiet detail. Passing i rather than i + 1 into the recursive call is what allows a number to be reused. Pass i + 1 and you've written a different problem, combinations without repetition. Same frame, one parameter changes the meaning.
Why undoing state is the whole game
With the frame in hand, the three problem shapes read as one idea seen from different angles:
- Unconditional enumeration, like all subsets, has no constraint, so you walk the whole tree and every node is an answer.
- Conditional enumeration, like Combination Sum or valid parentheses, prunes branches that break a rule mid build.
- Backtracking search, like N-Queens or Sudoku, looks for configurations under a global constraint and prunes hardest.
All three run the same choose, check, undo loop. The undo is what lets one mutable structure stand in for every node of the tree without the nodes contaminating each other. That's the thing I ended up rebuilding my own approach around.
It also reframes how the three shapes relate. They aren't three separate algorithms to learn. They're one loop with the constraint check dialled from off (subsets) to mid build (Combination Sum) to every level (N-Queens). Seeing them as one thing meant a new problem stopped being a blank page. The question became which shape it was and what the constraint was, and the frame handled the rest.
What I'd tell someone stuck on this
If you're losing time to backtracking that returns wrong answers, the fix is almost never more practice on harder problems. Grinding ten more search problems with the same blind spot just produces ten more silently wrong solutions. The thing standing between you and reliable backtracking is usually one missing line, not a missing concept. It's two habits. First, write the undo line at the same moment you write the choose line, as a pair, before anything else in the loop. Second, trace one full branch on paper and confirm the shared state looks identical before and after the recursive call.
And if the recursion itself still feels unstable underneath all this, that's worth shoring up first, because backtracking is just recursion with the choose, check, undo wrapper on top. Going back through the recursion lessons before touching backtracking again is what makes the wrapper feel mechanical instead of magical.
I originally posted this on my own blog, a slightly longer version with the N-Queens trace and a few more worked examples.
What's a bug that taught you more than the algorithm itself? For a lot of people backtracking is the one where a missing undo quietly breaks everything.