Introduction to Backtracking

Backtracking is a systematic way to explore all possible solutions to a problem by making choices, exploring their consequences, and undoing (backtracking) when they don't lead to a solution.

The Core Idea

Think of backtracking like exploring a maze:

  1. Try a path
  2. If it leads to a dead end, go back
  3. Try a different path
  4. Repeat until you find the exit (or explore all paths)
Start → Choice 1 → Choice 2 → Choice 3 → Solution ✓
     ↓
     Choice 2 → Dead end ✗ (backtrack)
     ↓
     Choice 3 → Choice 4 → Solution ✓

When to Use Backtracking

Look for these keywords:

  • "All possible combinations/permutations"
  • "Generate all..."
  • "Find all solutions"
  • "Count all ways to..."
  • Problems with choices and constraints

Problem Types

1. Generate All Solutions

  • All permutations of array
  • All subsets of set
  • All combinations that sum to target

2. Decision Problems

  • N-Queens placement
  • Sudoku solver
  • Word search in grid

3. Optimization with Exploration

  • Path finding with constraints
  • Resource allocation
  • Scheduling problems

The Backtracking Process

def backtrack(state):
    # 1. Base case: found solution
    if is_solution(state):
        save_solution(state)
        return

    # 2. Try all possible choices
    for choice in get_choices(state):
        # 3. Make choice
        make_choice(choice, state)

        # 4. Explore consequences
        backtrack(state)

        # 5. Undo choice (backtrack)
        undo_choice(choice, state)

Simple Example: Generate Binary Strings

Problem: Generate all binary strings of length n.

def generate_binary(n):
    result = []
    current = []

    def backtrack():
        # Base case: string complete
        if len(current) == n:
            result.append(''.join(current))
            return

        # Try adding '0'
        current.append('0')
        backtrack()
        current.pop()  # Undo

        # Try adding '1'
        current.append('1')
        backtrack()
        current.pop()  # Undo

    backtrack()
    return result

print(generate_binary(3))
# ['000', '001', '010', '011', '100', '101', '110', '111']

Trace for n=2:

Start: []
  Add '0': ['0']
    Add '0': ['0', '0'] → "00" ✓
    Remove '0': ['0']
    Add '1': ['0', '1'] → "01" ✓
    Remove '1': ['0']
  Remove '0': []
  Add '1': ['1']
    Add '0': ['1', '0'] → "10" ✓
    Remove '0': ['1']
    Add '1': ['1', '1'] → "11" ✓
    Remove '1': ['1']
  Remove '1': []

Key Characteristics

1. Recursive Structure

Backtracking uses recursion to explore possibilities.

2. State Management

You maintain and modify state as you explore.

3. Choice and Consequence

Make a choice, see where it leads, undo if necessary.

4. Pruning

Stop exploring paths that can't lead to solutions (optimization).

Backtracking vs. Other Approaches

vs. Brute Force

  • Brute Force: Generate all possibilities, then check
  • Backtracking: Build solutions incrementally, abandon bad paths early

vs. Dynamic Programming

  • DP: Overlapping subproblems, optimal substructure
  • Backtracking: Exploring choices, generating all solutions

vs. Greedy

  • Greedy: Make best local choice
  • Backtracking: Explore all choices systematically

Time Complexity

Backtracking is often exponential because it explores many possibilities:

  • Permutations: O(n!)
  • Subsets: O(2ⁿ)
  • Combinations: O(2ⁿ) or O(C(n,k))

But pruning can significantly reduce the search space!

Example: Generate Permutations

def permutations(nums):
    result = []
    current = []
    used = [False] * len(nums)

    def backtrack():
        # Base case
        if len(current) == len(nums):
            result.append(current[:])  # Make a copy!
            return

        # Try each number
        for i in range(len(nums)):
            if used[i]:
                continue  # Skip if already used

            # Choose
            current.append(nums[i])
            used[i] = True

            # Explore
            backtrack()

            # Unchoose
            current.pop()
            used[i] = False

    backtrack()
    return result

print(permutations([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Common Mistakes

❌ Forgetting to Backtrack

def wrong(nums):
    result = []
    current = []

    def backtrack():
        if len(current) == len(nums):
            result.append(current)  # Wrong! Will be modified
            return

        for num in nums:
            current.append(num)
            backtrack()
            # Forgot to remove! ❌

    backtrack()
    return result

✅ Correct Version

def correct(nums):
    result = []
    current = []

    def backtrack():
        if len(current) == len(nums):
            result.append(current[:])  # Copy!
            return

        for num in nums:
            current.append(num)
            backtrack()
            current.pop()  # Backtrack ✓

    backtrack()
    return result

Visualization

                    []
                 /      \
               [1]      [2]      [3]
              /  \      / \      / \
           [1,2][1,3][2,1][2,3][3,1][3,2]
             |    |    |    |    |    |
          [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

Each branch represents a choice. We explore depth-first and backtrack when done.

Key Takeaway

Backtracking is about systematically exploring possibilities. The key insight: make a choice, explore it fully, then undo it and try the next choice. This "choose-explore-unchoose" pattern is the heart of backtracking.

PreviousBacktracking Fundamentals
NextThe Backtracking Template