Common Backtracking Mistakes and Fixes

Why a Checklist Helps

Backtracking code is short, and most bugs are one missing line. The output is usually plausible — the right shape, just wrong contents — so the bug is easy to miss. This page collects the mistakes that show up most often, with a buggy and fixed run of each side by side.

THE FIVE-LINE CHECKLIST — read your code against it before running:

  □ Do I store a COPY of the path, not the path itself?
  □ Is every choose (add / mark / swap) undone on every code path?
  □ Does the loop start where it should (start index vs 0)?
  □ Does my duplicate check compare against the right index?
  □ If I only need one answer, do I stop as soon as I find it?

Mistake 1: Storing the Path by Reference

BUGGY:   results.append(path)
FIXED:   results.append(path[:])            Python
         results.add(new ArrayList<>(path)) Java
         results.push([...path])            JavaScript
         results.push_back(path)            C++ (copies — unless you store a pointer)

What goes wrong:
  results = [path, path, path, path]   ← four references to ONE list
  the search pops everything on the way back → path = []
  printing results shows [] [] [] []

Mistake 2: Forgetting the Undo

BUGGY:                          FIXED:
  path.append(x)                  path.append(x)
  recurse(...)                    recurse(...)
                                  path.pop()          ← un-choose

What goes wrong:
  [1] → [1,2] → [1,2,3] → back at [1,2] level, but path is still [1,2,3]
  next sibling appends 3 again → [1,2,3,3] ... answers keep growing

The same applies to every kind of state: used[j] = false, board[r][c] = saved, unmarking columns and diagonals, swapping back.

Mistake 3: Looping From 0 in a Combination Search

BUGGY:   for j in 0 .. n-1:          ← any value can follow any other
FIXED:   for j in start .. n-1:      ← values appear in input order

Coins [2, 3], make 7:
  buggy → [2,2,3] [2,3,2] [3,2,2]    (one group, three orderings)
  fixed → [2,2,3]

Use loop-from-0 only when order matters (orderings / permutations) — and then use a used array.

Mistake 4: Duplicate Check Against the Wrong Index

BUGGY:   if j > 0     and nums[j] == nums[j-1]: continue
FIXED:   if j > start and nums[j] == nums[j-1]: continue

nums = [1, 2, 2] (sorted)
  buggy → misses [1, 2, 2] and [2, 2]
  fixed → [] [1] [1,2] [1,2,2] [2] [2,2]

The rule is "don't START two sibling branches with the same value".
The first value at each level (j == start) must always be allowed.

Seeing All Four in One Run

Output:
1 buggy: [] [] [] []
1 fixed: [] [1] [1, 2] [2]
2 buggy: [] [1] [1, 2] [1, 2, 3] [1, 2, 3, 3] [1, 2, 3, 3, 2] [1, 2, 3, 3, 2, 3] [1, 2, 3, 3, 2, 3, 3]
2 fixed: [] [1] [1, 2] [1, 2, 3] [1, 3] [2] [2, 3] [3]
3 buggy: [2, 2, 3] [2, 3, 2] [3, 2, 2]
3 fixed: [2, 2, 3]
4 buggy: [] [1] [1, 2] [2]
4 fixed: [] [1] [1, 2] [1, 2, 2] [2] [2, 2]

Each buggy line has the right count of entries or the right kind of entries — which is exactly why these bugs slip through. Always compare against a small hand-worked answer.

Mistake 5: Not Stopping After the First Answer

When the task is "find any valid arrangement" (Sudoku, a single N-Queens board, a word on a grid), the search must stop as soon as one is found.

BUGGY:                                  FIXED:
  def solve(state):                       def solve(state):
      if complete: print(state); return       if complete: return True
      for option in options:                  for option in options:
          apply(option)                           apply(option)
          solve(state)                            if solve(state): return True
          undo(option)                            undo(option)
                                              return False

The buggy version prints the solution and then keeps searching —
for Sudoku that can mean millions of extra calls, and the grid
is erased by the undo steps on the way back.

Mistake 6: Undo Doesn't Mirror the Choose

The undo must reverse exactly what the choose step did — every array, counter, and mark.

CHOOSE                                   UNDO
cols[c] = d1[r-c+n-1] = d2[r+c] = True   cols[c] = d1[r-c+n-1] = d2[r+c] = False
used[j] = True; path.append(x)           path.pop(); used[j] = False
sum += x; count += 1                     sum -= x; count -= 1
board[r][c] = '#'                        board[r][c] = saved   (not a constant!)

A tidy habit: write the undo line IMMEDIATELY after writing the
choose line, before writing the recursive call between them.

Passing new values as arguments (e.g. solve(i + 1, remaining - x)) avoids the undo for those values completely — the caller's copy is never changed.

Mistake 7: Pruning That Removes Valid Answers

"break when the running sum exceeds the target"
  ✓ valid if all values are positive and the input is SORTED
  ✗ wrong if values can be negative — a later value could bring the sum back

"skip equal neighbours"
  ✓ valid only after SORTING
  ✗ on unsorted input it skips nothing useful — and may skip wrong things
     if combined with other assumptions

Before adding a prune, state the reason it is safe in one sentence.
If you can't, it probably isn't.

Mistake 8: Exponential Search Where DP Fits

SYMPTOM: correct on small inputs, times out on n = 40 or target = 10,000
CAUSE:   the question only asks for a COUNT or a BEST value, and the
         same (index, remaining) state is reached by many paths
FIX:     memoize on the state, or rewrite as a DP table

The Memoization page walks through adding a cache to an existing recursive search.

A Debugging Routine That Works

1. Shrink the input until the bug still shows (often n = 2 or 3).
2. Work out the correct answer by hand.
3. Print each call with indentation = depth, plus the current path.
4. Compare the printed tree with the tree you expected to draw.
   The first line that differs points straight at the bug:
     - path contains an extra element  → missing undo
     - same group in a new order       → loop start is wrong
     - a subtree is missing            → prune too aggressive / wrong dedupe
     - leaves look right but results
       are all the same                → stored a reference

The Decision Tree Thinking page shows exactly this kind of indented trace.

Interview Questions

Q: Your subset generator returns the right number of results, but they are all empty lists. What happened?

The function stored the shared path object rather than a copy. All entries are the same list, which is empty once the recursion has fully unwound. Storing new ArrayList<>(path) (or the language's equivalent) fixes it.

Q: How do you make sure every choose step is undone, even with early continue or return statements?

Keep the choose, recurse, and undo as three consecutive lines with nothing in between that can skip the undo. Do validity checks and continues before the choose step. For a "find one answer" search, returning true without undoing is acceptable because the state is the answer.

Q: When is it acceptable to not undo state at all?

When the state is passed by value — for example, an index, a remaining sum, or an immutable string built with concatenation. Each call gets its own copy, so nothing needs reversing. The trade-off is extra copying; mutable shared state plus explicit undo is usually faster.

Summary

• ›Store copies, never the working list.
• ›Every choose needs a matching undo that mirrors it exactly.
• ›Loop start: start for groups, 0 + used array for orderings.
• ›Dedupe: sort first, then compare with j > start.
• ›Stop early when only one answer is needed.
• ›State the reason every prune is safe; switch to DP when only counts or optima are needed.

Ready to practise? The Backtracking problems cover subsets, orderings, combinations, board puzzles, and grid searches.