Link Search Menu Expand Document

Introduction to Backtracking

A new kind of recursion

So far, the recursive functions we have written have had a common trait: at each step, there is exactly one thing to do. In factorial, you multiply by n and recurse on n - 1. In Fibonacci, you add two recursive results together. In string reversal, you move one character and recurse on the rest. There is never a moment where you have to choose between multiple options, not knowing which one is correct.

Backtracking is a recursive technique for problems where you do face choices, and you don’t know which choice is right ahead of time. The idea is:

  1. Try one of the options.
  2. Recurse to see if that choice eventually leads to a solution.
  3. If it does, great — we are done.
  4. If it doesn’t, undo the choice (this is the “backtracking” part) and try the next option.
  5. If none of the options work, report failure.

This is different from the recursion we have seen before. In factorial, there is nothing to “try” — you just do it. In backtracking, you might go down a long path of recursive calls, discover it was a dead end, undo everything, and start over with a different choice. Think of it like solving a jigsaw puzzle: imagine a large section of the puzzle that is already completed, and we try to fit a new piece in. If the piece doesn’t fit, we remove it (backtrack) and try another piece in its place.

Example: Double or add?

Here is a simple problem that requires backtracking:

Start at 1. On each step, you can either double the current number or add 3. Can you reach the target number exactly without going over?

For example, if the target is 8:

  • 1 → double → 2 → double → 4 → double → 8. Yes!

If the target is 11:

  • 1 → double → 2 → double → 4 → double → 8 → … now what? Doubling gives 16 (too big). Adding 3 gives 11. Yes!
  • So the path is: 1 → 2 → 4 → 8 → 11.

But what if the target is 6?

  • 1 → double → 2 → double → 4 → double → 8 (overshot!)
    • Backtrack to 4.
  • 4 → add 3 → 7 (not 6, and both 14 and 10 overshoot)
    • Backtrack to 4. No more options at 4, so backtrack to 2.
  • 2 → add 3 → 5 → double → 10 (overshot!)
    • Backtrack to 5.
  • 5 → add 3 → 8 (overshot!)
    • Backtrack to 5. No more options at 5, so backtrack to 2. No more options at 2, so backtrack to 1.
  • 1 → add 3 → 4 → (we already know 4 doesn’t work)
    • …and so on.

What is happening here is we are trying one option, following it as far as it goes, and when it fails, we come back and try the other option. That is backtracking.

The code

Here is the pseudocode for this problem:

function doubleOrAdd(current, target):
    // Base cases
    if current == target:
        return true             // We made it!
    if current > target:
        return false            // We overshot, this path failed.

    // Try doubling
    if doubleOrAdd(current * 2, target):
        return true             // Doubling eventually worked!

    // Doubling didn't work --- try adding 3
    if doubleOrAdd(current + 3, target):
        return true             // Adding 3 eventually worked!

    // Neither option worked from here
    return false

Take a look at the structure of this function. There is an if around each recursive call. We are testing whether a recursive call succeeds, and using that result to decide what to do next. Compare this to factorial:

function factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)    // no "if" --- we just do it

In factorial, you always make the recursive call. In backtracking, you make a recursive call, check if it worked, and if it didn’t, you try something else. This try-check-try-again structure is the defining pattern of backtracking.

Tracing the recursion

Let’s trace through doubleOrAdd(1, 11) step by step. Pay attention to how the recursion unfolds — when a path fails, we return to the previous call and try the other option.

doubleOrAdd(1, 11)
│  1 is not 11, and 1 < 11, so try doubling...
│
├── doubleOrAdd(2, 11)
│   │  2 is not 11, and 2 < 11, so try doubling...
│   │
│   ├── doubleOrAdd(4, 11)
│   │   │  4 is not 11, and 4 < 11, so try doubling...
│   │   │
│   │   ├── doubleOrAdd(8, 11)
│   │   │   │  8 is not 11, and 8 < 11, so try doubling...
│   │   │   │
│   │   │   ├── doubleOrAdd(16, 11)
│   │   │   │      16 > 11, return false.  ← overshot!
│   │   │   │
│   │   │   │  Doubling didn't work. Try adding 3...
│   │   │   │
│   │   │   ├── doubleOrAdd(11, 11)
│   │   │   │      11 == 11, return true!  ← found it!
│   │   │   │
│   │   │   │  Adding 3 worked! return true.
│   │   │
│   │   │  Doubling worked! return true.
│   │
│   │  Doubling worked! return true.
│
│  Doubling worked! return true.

Result: true
Path taken: 1 → 2 → 4 → 8 → 11

doubleOrAdd(16, 11) returned false, which caused doubleOrAdd(8, 11) to abandon doubling and try adding 3 instead. That is the backtracking in action.

A case with more backtracking

Now let’s trace doubleOrAdd(1, 14) to see what happens when the first several attempts fail. (This trace only shows the important parts — the full diagram is larger.)

doubleOrAdd(1, 14)
├── doubleOrAdd(2, 14)          try doubling
│   ├── doubleOrAdd(4, 14)      try doubling
│   │   ├── doubleOrAdd(8, 14)  try doubling
│   │   │   ├── doubleOrAdd(16, 14)  → false (overshot)
│   │   │   ├── doubleOrAdd(11, 14)  try adding 3
│   │   │   |   ├── doubleOrAdd(22, 14)  → false (overshot)
│   │   │   |   └── doubleOrAdd(14, 14)  → TRUE! 
│   │   │   │
│   │   │   return true
│   │   return true
│   return true
return true

Path taken: 1 → 2 → 4 → 8 → 11 → 14

Here the recursion tried doubling 8 (got 16, too big), backtracked, tried adding 3 (got 11), then tried doubling 11 (got 22, too big), backtracked again, tried adding 3 (got 14, the target).

An impossible case

What about doubleOrAdd(1, 6)? No combination of doubling and adding 3 starting from 1 will ever hit exactly 6. The recursion will try every possible path, and every one of them will overshoot or miss. In this case, every branch eventually returns false, and the final answer is false. No backtracking path succeeds.

Try tracing this one yourself to see why it is impossible.

Recovering the path

The doubleOrAdd function tells us whether we can reach the target, but it does not tell us how. We know the answer to “can I reach 14?” is true, but what was the sequence of operations? Was it double, double, double, add, add? Something else?

In many backtracking problems, we care not just about whether a solution exists, but about the specific sequence of choices that produces it. To recover this, we change the function to return a string instead of a boolean. The string will record the choices we made along the way. If no solution exists, we return a special failure string: "X".

We will use "D" for double, "A" for add 3, and "!" for success (meaning we reached the target). So a solution to target 11 would look like "DDDA!" (double, double, double, add 3, success), meaning 1 → 2 → 4 → 8 → 11.

Here is the pseudocode:

function doubleOrAddWithSolution(current, target):
    // Base cases
    if current == target:
        return "!"              // We're here! Signal success.
    if current > target:
        return "X"              // Overshot. Failure.

    // Try doubling
    result = doubleOrAddWithSolution(current * 2, target)
    if result != "X":
        return "D" + result     // Doubling worked! Prepend "D".

    // Doubling didn't work --- try adding 3
    result = doubleOrAddWithSolution(current + 3, target)
    if result != "X":
        return "A" + result     // Adding 3 worked! Prepend "A".

    // Neither option worked from here
    return "X"

Compare this to the boolean version. The structure is the same. Every place that returned true now returns a string of directions (ending in "!"). Every place that returned false now returns "X". Instead of checking if doubleOrAdd(...):, we check if result != "X":. The backtracking logic has not changed — we just changed what we are carrying back through the recursion.

Tracing the path version

Let’s trace doubleOrAddWithSolution(1, 14):

doubleOrAddWithSolution(1, 14)
├── doubleOrAddWithSolution(2, 14)                try doubling
│   ├── doubleOrAddWithSolution(4, 14)            try doubling
│   │   ├── doubleOrAddWithSolution(8, 14)        try doubling
│   │   │   ├── doubleOrAddWithSolution(16, 14)   → "X" (overshot)
│   │   │   │
│   │   │   │  Doubling failed. Try adding 3...
│   │   │   │
│   │   │   ├── doubleOrAddWithSolution(11, 14)   try adding 3
│   │   │   |   ├── doubleOrAddWithSolution(22, 14)  → "X" (overshot)
│   │   │   |   │
│   │   │   |   │  Doubling failed. Try adding 3...
│   │   │   |   │
│   │   │   |   └── doubleOrAddWithSolution(14, 14)  → "!" (target reached!)
│   │   │   |   │
│   │   │   |   return "A" + "!" = "A!"
│   │   │   │
│   │   │   return "A" + "A!" = "AA!"
│   │   │
│   │   return "D" + "AA!" = "DAA!"
│   │
│   return "D" + "DAA!" = "DDAA!"
│
return "D" + "DDAA!" = "DDDAA!"

Result: "DDDAA!"
Meaning: double, double, double, add 3, add 3, success
Path:    1 → 2 → 4 → 8 → 11 → 14  ✓

The string builds up as the recursion unwinds. The deepest successful call returns "!" (success — we are at the target). Each call above it prepends its own choice: "A", then "A", then "D", then "D", then "D". By the time we are back at the top, we have the full path: "DDDAA!".

If the target were 6, every path fails, and "X" propagates all the way back up. The final answer is "X", meaning no sequence of operations works. So when you get your answer back, you check: is it "X"? If not, it is a sequence of D’s and A’s ending in !, and you know both that a solution exists and exactly what it is.

Two formulations, one pattern

We have now seen two ways to write the same backtracking algorithm:

  1. Boolean version: Returns true/false. Answers “can it be done?”
  2. Path version: Returns a string (or "X" for failure). Answers “can it be done, and if so, how?”

These are not really different algorithms. They have the same structure, explore the same paths, and backtrack in the same places. The only difference is what they carry back through the return values. You will implement both formulations in the main project for this assignment.

The general backtracking pattern

Every backtracking problem you will encounter in this course follows one of these two patterns:

Boolean version (can it be done?):

function solve(state):
    if state is the goal:
        return true
    if state is invalid:
        return false

    for each option available from state:
        if solve(state after applying option):
            return true
    return false

Path version (how is it done?):

function solve(state):
    if state is the goal:
        return "!" (success --- we are done)
    if state is invalid:
        return "X" (failure)

    for each option available from state:
        result = solve(state after applying option)
        if result != "X":
            return description of option + result
    return "X"

The specific details change — what “state” is, what the “options” are, what makes a state “invalid” — but the structure is always the same. You will see both patterns again in the main project.

Summary

A few things to keep in mind as you move forward:

  • Backtracking means: try a choice, see if it leads to a solution, and if not, undo it and try the next choice.

  • The if around the recursive call is new. You are testing whether a recursive path works, not just computing a result.

  • Most recursive calls in a backtracking algorithm return false (or "X"). That is not a bug — it is the algorithm working correctly, exploring and eliminating dead ends.

  • You do not write explicit “go back” code. When a recursive call returns false, the previous call is still sitting there waiting, and it simply moves on to the next option. The call stack is the backtracking mechanism.

  • If you can write the boolean version, converting it to return the path is mostly mechanical: replace true with "!", replace false with "X", and prepend your choice to the result as it comes back up.