Backtracking Fundamentals

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 3 Time to complete: ~25 minutes

Table of Contents

1. What Is Backtracking?
2. The General Template
3. Worked Example: Generate All Binary Strings
4. Why "Undo" Matters
5. Complexity of Backtracking
6. Summary & Next Steps

1. What Is Backtracking?

Backtracking is recursion applied to a specific shape of problem: build a solution one choice at a time, and if a choice leads somewhere invalid or the exploration is finished, undo it and try the next option. It's how you'd solve a maze by hand — walk forward, and if you hit a dead end, walk back to the last junction and try a different path, rather than starting over.

The three moves, repeated at every step:

1. CHOOSE   — pick one option from the choices available right now
2. EXPLORE  — recurse with that choice made
3. UNCHOOSE — undo the choice before trying the next option

2. The General Template

Every backtracking problem in this chapter and the next follows this same skeleton:

def backtrack(path, choices):
    if is_complete(path):            # base case: a full solution has been built
        record_solution(path)
        return
 
    for choice in choices:
        if not is_valid(choice, path):
            continue                  # skip choices that can't possibly work
 
        path.append(choice)           # 1. CHOOSE
        backtrack(path, remaining_choices(choices, choice))  # 2. EXPLORE
        path.pop()                    # 3. UNCHOOSE — undo before the next option

The recursion tree here looks like the branching Fibonacci tree from Chapter 2 — except instead of every branch being explored blindly, is_valid lets you skip branches that can't lead to a solution, cutting the tree down before it gets explored. That skipping step is called pruning, and it's what separates efficient backtracking from brute-force enumeration.

3. Worked Example: Generate All Binary Strings

A minimal, fully worked application of the template — build every binary string of length n:

def generate_binary_strings(n):
    results = []
 
    def backtrack(path):
        if len(path) == n:                # base case: string is the right length
            results.append("".join(path))
            return
 
        for digit in ("0", "1"):          # the choices at this step
            path.append(digit)             # 1. CHOOSE
            backtrack(path)                 # 2. EXPLORE
            path.pop()                       # 3. UNCHOOSE
 
    backtrack([])
    return results
 
print(generate_binary_strings(3))
# ['000', '001', '010', '011', '100', '101', '110', '111']

Trace it by hand for n = 2: backtrack([]) chooses "0", explores down to backtrack(["0"]), which chooses "0" again, hits the base case at ["0", "0"], records "00", returns, unchooses back to ["0"], then chooses "1" for the second position, records "01", unchooses all the way back to [], then starts over choosing "1" first. Every path through the tree is explored exactly once.

4. Why "Undo" Matters

The path.pop() step is easy to skip mentally but is not optional — path is a single shared list being mutated throughout the recursion, not a fresh copy per call (that distinction matters a great deal, and mirrors the aliasing behavior from Python Module 1's Lists chapter). Without undoing the choice, every subsequent branch would incorrectly build on top of choices that should have been discarded.

# Without the undo step, this would build "0" then wrongly append onto
# the SAME list for every following branch, corrupting every other path:
path.append(digit)
backtrack(path)
# path.pop()   ← forgetting this line breaks every branch after the first

5. Complexity of Backtracking

Backtracking's complexity is almost always expressed as (number of leaves in the recursion tree) × (work done per leaf). For generate_binary_strings(n), there are 2ⁿ possible strings (2 choices at each of n positions — an O(2ⁿ) tree shape, same growth pattern as naive Fibonacci from Chapter 2), and each one costs O(n) to join into a string, giving roughly O(n · 2ⁿ) overall. This kind of exponential shape is expected and often unavoidable for backtracking — the goal of pruning (skipping invalid choices early via is_valid) is to shrink the constant behind that exponential in practice, not to change its fundamental shape.

6. Summary & Next Steps

Key Takeaways

• Backtracking follows choose → explore → unchoose, built on top of the recursion you already know from Chapters 1-3.
• Pruning (skipping choices that can't lead to a valid solution via an is_valid check) is what makes backtracking practical rather than pure brute force.
• The "unchoose" step is required, not stylistic — without it, mutable shared state leaks between branches that should be independent.
• Backtracking complexity is typically exponential (tree size) times per-leaf work — the same shape as tree-shaped recursion from Chapter 2, deliberately embraced because many of these problems have no faster general solution.

Concept Check

1. What are the three steps of the backtracking template, and what does each one do?
2. Why does forgetting path.pop() corrupt results, given that path is being mutated rather than copied?
3. What role does is_valid (pruning) play in keeping backtracking practical?

Next Chapter

→ Chapter 5: Classic Backtracking Problems

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index