Backtracking Basics

What Is Backtracking?

Backtracking is a way of building an answer one decision at a time, and stepping back to the previous decision as soon as the current path stops making sense.

Think of filling in a crossword with a pencil. You write a word, move to the next clue, and if nothing fits there, you erase the last word and try a different one. You never throw away the whole grid — you only rewind as far as you need to.

THE SHAPE OF EVERY BACKTRACKING SEARCH:

  solve(partial answer):
      if partial answer is complete:
          record it
          return
      for each option that is allowed right now:
          CHOOSE    → apply the option to the partial answer
          EXPLORE   → solve(bigger partial answer)
          UN-CHOOSE → remove the option again

  The un-choose step is what makes it "back"-tracking:
  the next option starts from a clean slate.

Backtracking is the go-to tool when a problem says:

• ›"List all …" (all subsets, all orderings, all valid layouts)
• ›"Find any arrangement that satisfies these rules" (puzzles, schedules, colourings)
• ›"Count the ways …" when the rules are too irregular for a formula

Backtracking vs Plain Recursion

Every backtracking solution is recursive, but not every recursive function backtracks.

PLAIN RECURSION (e.g. factorial, tree height):
  - One way forward at each call
  - No shared state to restore
  - Answer is returned upward and combined

BACKTRACKING:
  - Several options at each call (a loop over choices)
  - A shared "partial answer" that is modified, then restored
  - Answers are usually collected on the way down (at the leaves)

The extra ingredient is mutable shared state plus the undo step. Without the undo, choices from one branch leak into the next and the results become nonsense.

A First Example: Lights With No Two Neighbours On

Imagine a row of n lights. Each light is either off (0) or on (1). A layout is valid if no two neighbouring lights are both on. Print every valid layout.

n = 4, valid layouts:

  0000  0001  0010  0100  0101  1000  1001  1010

Invalid examples: 0011, 1100, 1110 (two neighbours on)

Thinking It Through

DECISION per level:   which state does light i get?
OPTIONS:              0 is always allowed
                      1 is allowed only if light i-1 is not 1
COMPLETE WHEN:        all n lights have a state
UNDO:                 remove the last character from the layout

Search tree for n = 3 (✂ = pruned before it is even built):

                        ""
                 /              \
               "0"              "1"
             /     \           /    \
          "00"     "01"     "10"    ✂ "11"
          /  \     /  \     /  \
       000  001  010 ✂011 100  101

  Valid leaves: 000, 001, 010, 100, 101  → 5 layouts

The ✂ marks are pruning: the check previous light is not 1 happens before the recursive call, so the bad branch is never entered. Nothing below it is ever generated.

Output:
n=1 (2): 0 1
n=2 (3): 00 01 10
n=3 (5): 000 001 010 100 101
n=4 (8): 0000 0001 0010 0100 0101 1000 1001 1010

Notice the counts: 2, 3, 5, 8. Each count is the sum of the two before it. That is a strong hint that if you only needed the count, dynamic programming would do it in O(n). Backtracking is the right tool here because the task asks you to list every layout.

The Reusable Template

Almost every backtracking problem fits this skeleton. Only four things change from problem to problem.

def backtrack(state):
    if IS_COMPLETE(state):                 ← (1) when is an answer finished?
        results.append(COPY(state))
        return
    for option in OPTIONS(state):          ← (2) what can I try next?
        if not IS_VALID(state, option):    ← (3) which options break a rule? (pruning)
            continue
        APPLY(state, option)               ← (4) how do I choose ...
        backtrack(state)
        UNDO(state, option)                ←     ... and un-choose?

Pruning: Why Backtracking Is Faster Than Brute Force

Brute force builds every complete candidate and checks it at the end. Backtracking checks rules while building, and abandons a candidate the moment it breaks one.

BRUTE FORCE for the lights problem, n = 20:
  Build all 2^20 = 1,048,576 layouts, then filter.

BACKTRACKING with the "previous light" check:
  Never builds a layout containing "11".
  Reaches only 17,711 complete layouts (plus their prefixes).

The earlier you can detect a dead end, the more you save:
a branch cut at depth d removes everything beneath it —
for a binary tree that is roughly 2^(n-d) nodes in one check.

Good pruning comes from asking: "Given the partial answer, can I already prove that no completion will work?" If yes, return immediately.

When to Reach for Backtracking

STRONG SIGNALS:
  ✓ "Return all ..." / "list every ..."        → you must enumerate
  ✓ Small input limits (n ≤ 10–20)             → exponential is acceptable
  ✓ Rules that are checked on a partial answer  → natural pruning
  ✓ Puzzles: placement, filling, colouring      → classic constraint search

WEAK SIGNALS (think about another technique first):
  ✗ "Return the number of ways" with n up to 10^5  → probably DP
  ✗ "Return the minimum / maximum" with large n    → DP, greedy, or graph search
  ✗ The same sub-state is reached many times       → add memoization (= DP)

Common Mistakes

Forgetting the undo step. If you append to the path and never remove, the next option starts with stale data. Every APPLY must be matched by exactly one UNDO on every code path, including early continues.

Storing the path by reference. results.append(path) stores the same list object every time. After the search, all entries show the final state of path (usually empty). Store path[:], new ArrayList<>(path), or a joined string.

Checking rules only at the leaves. That is brute force wearing a recursion costume. Move every check you can to the moment an option is chosen.

Unbounded recursion. Every call must move closer to the "complete" condition — usually by advancing an index or growing the path by one. If a branch can call itself with the same state, it never ends.

Interview Questions

Q: What makes an algorithm "backtracking" rather than ordinary recursion?

A backtracking function explores several options at each level and shares one mutable partial answer between them. It applies an option, recurses, then reverses that option so the next sibling sees an unchanged state. Ordinary recursion usually has one path forward and combines return values instead of mutating shared state.

Q: How do you estimate the running time of a backtracking solution?

Multiply the branching factor at each level across the depth to bound the number of nodes in the search tree, then multiply by the work per node (often the cost of copying an answer at the leaves). Subsets give about 2ⁿ leaves, orderings give n! leaves. Pruning lowers the real number, but the worst-case bound is usually quoted without it.

Q: When should a backtracking solution be turned into dynamic programming?

When the task only needs a count or a best value and the same partial state (for example "index i with remaining sum s") is reached through many different paths. Caching the answer for each state removes the repeated work. If the task needs every answer listed, the output itself is exponential, and backtracking remains the natural choice.

Summary

• ›Backtracking builds an answer one decision at a time and undoes a decision when the path cannot succeed.
• ›Every solution follows choose → explore → un-choose.
• ›Four things define a problem: complete condition, options, validity check, and state with its undo.
• ›Pruning — rejecting a partial answer early — is what separates backtracking from brute force.
• ›Store copies of answers, never the shared working list.

Next, Decision Tree Thinking shows how to sketch the search tree on paper before writing any code — the single most useful habit for getting backtracking right the first time.