The Backtracking Template

Most backtracking problems follow a similar pattern. Learn this template and you can solve dozens of problems!

The Universal Template

def backtracking_problem(input_data):
    result = []
    current = []  # or other state

    def backtrack(start_index):
        # 1. BASE CASE: Valid solution found
        if is_valid_solution(current):
            result.append(current[:])  # Make a copy!
            return

        # 2. ITERATE: Try all possible choices
        for i in range(start_index, len(input_data)):
            # 3. PRUNE: Skip invalid choices
            if not is_valid_choice(i, current):
                continue

            # 4. CHOOSE: Make the choice
            make_choice(i, current)

            # 5. EXPLORE: Recurse with updated state
            backtrack(i + 1)  # or i, depending on problem

            # 6. UNCHOOSE: Undo the choice (backtrack)
            undo_choice(i, current)

    backtrack(0)
    return result

Template Components Explained

1. Result Container

result = []  # Stores all valid solutions

2. Current State

current = []  # Current partial solution being built

Could be:

• List (for combinations, permutations)
• String (for string problems)
• Grid (for board problems)
• Set (for tracking used elements)

3. Base Case

if is_valid_solution(current):
    result.append(current[:])  # Make a copy!
    return

Important: Always copy when saving! Otherwise, you save a reference that gets modified.

4. Choice Iteration

for i in range(start_index, len(input_data)):

Starting point varies:

• start_index: For combinations (no duplicates in solution)
• 0: For permutations (can reuse earlier elements)
• current position: For grid problems

5. Pruning (Optional but Important)

if not is_valid_choice(i, current):
    continue

Skip choices that:

• Violate constraints
• Lead to duplicates
• Can't possibly lead to solutions

6. Choose-Explore-Unchoose

make_choice(i, current)      # Add to state
backtrack(i + 1)             # Recurse
undo_choice(i, current)      # Remove from state

This is the heart of backtracking!

Example 1: Subsets

Problem: Generate all subsets of an array.

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

    def backtrack(start):
        # Every state is a valid subset
        result.append(current[:])

        for i in range(start, len(nums)):
            # Choose
            current.append(nums[i])

            # Explore
            backtrack(i + 1)  # i+1: don't reuse same element

            # Unchoose
            current.pop()

    backtrack(0)
    return result

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

Why start from i+1? We want each element at most once, so we don't go back to earlier indices.

Example 2: Permutations

Problem: Generate all permutations of an array.

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

    def backtrack():
        # Base case: used all numbers
        if len(current) == len(nums):
            result.append(current[:])
            return

        for i in range(len(nums)):
            # Prune: skip if already used
            if used[i]:
                continue

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

            # Explore
            backtrack()  # Start from 0 each time

            # 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]]

Why no start parameter? Permutations can use any element at any position, so we always check all elements.

Example 3: Combination Sum

Problem: Find all combinations that sum to target. Can reuse numbers.

def combination_sum(candidates, target):
    result = []
    current = []

    def backtrack(start, remaining):
        # Base case: found exact sum
        if remaining == 0:
            result.append(current[:])
            return

        # Prune: sum exceeded
        if remaining < 0:
            return

        for i in range(start, len(candidates)):
            # Choose
            current.append(candidates[i])

            # Explore (i, not i+1, because we can reuse)
            backtrack(i, remaining - candidates[i])

            # Unchoose
            current.pop()

    backtrack(0, target)
    return result

print(combination_sum([2, 3, 6, 7], 7))
# [[2,2,3], [7]]

Why start from i? We can reuse the same number, so we pass i instead of i+1.

Template Variations

Variation 1: Find One Solution

def backtrack(start):
    if is_valid_solution(current):
        return True  # Found one, stop

    for i in range(start, len(input_data)):
        if not is_valid_choice(i):
            continue

        make_choice(i)
        if backtrack(i + 1):  # Found solution in recursion
            return True
        undo_choice(i)

    return False  # No solution found

Variation 2: Count Solutions

def backtrack(start):
    if is_valid_solution(current):
        return 1  # Count this solution

    count = 0
    for i in range(start, len(input_data)):
        if not is_valid_choice(i):
            continue

        make_choice(i)
        count += backtrack(i + 1)  # Add counts from recursion
        undo_choice(i)

    return count

Variation 3: Find Best Solution

def backtrack(start):
    if is_valid_solution(current):
        nonlocal best
        best = max(best, evaluate(current))
        return

    for i in range(start, len(input_data)):
        if not is_valid_choice(i):
            continue

        make_choice(i)
        backtrack(i + 1)
        undo_choice(i)

Decision Tree

Understanding the recursive calls as a tree helps:

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

• Each node is a state
• Each edge is a choice
• Leaves are complete solutions
• Backtracking = going up the tree

Common Parameters

Tips for Using the Template

1. Identify state: What do you need to track?
2. Define base case: When is a solution complete?
3. List choices: What can you add at each step?
4. Add pruning: What choices are invalid?
5. Decide recursion parameter: Reuse elements? Start from where?

Practice: Fill in the Blanks

def solve_problem(nums, target):
    result = []
    current = []

    def backtrack(start):
        # Base case: ???
        if ___________:
            result.append(_________)
            return

        # Try choices
        for i in range(________, ________):
            # Prune: ???
            if ___________:
                continue

            # Choose: ???
            __________

            # Explore: ???
            backtrack(________)

            # Unchoose: ???
            __________

    backtrack(0)
    return result

Key Takeaway

The backtracking template is your Swiss Army knife for "find all" problems. Learn it once, apply it everywhere. The differences between problems are usually just in the base case, pruning condition, and recursion parameter!