The Backtracking Template - Learning Module

Loading content...

0/279

The Universal Template Structure

One Template to Solve Them All

We've now explored the three fundamental phases of backtracking: Choose (make a decision), Explore (recurse with that decision), and Unchoose (undo the decision). Individually, each phase serves a specific purpose. Together, they form a universal template that can solve an remarkably diverse range of problems.

This template is your weapon against complexity. Once internalized, you can map any backtracking problem onto its structure, fill in the problem-specific details, and have a working solution. The template handles the traversal logic; you supply the problem semantics.

In this page, we'll crystallize the template into its canonical form, demonstrate how to map problems onto it, explore variations for different problem categories, and establish best practices for robust implementation.

What You Will Learn

By the end of this page, you will:

• Have memorized the canonical backtracking template • Know how to identify problems that fit the template • Understand how to customize the template for different problem types • Be able to map any backtracking problem onto the template structure • Have a mental checklist for implementing correct backtracking solutions

This completes your mastery of the backtracking template.

The Canonical Template

Here is the universal backtracking template in its purest form. Every backtracking algorithm is a variation of this structure:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def solve(problem_input):
    """
    Universal backtracking template.
    Returns all solutions (or first solution, with modification).
    """
    solutions = []                    # Accumulator for solutions
    state = create_initial_state()    # Track current partial solution
    
    def backtrack(progress_parameter):
        """
        The recursive backtracking function.
        progress_parameter: tracks how close we are to completion
        """
        
        # ════════════════════════════════════════════════════
        # BASE CASE: Check if solution is complete
        # ════════════════════════════════════════════════════
        if is_complete(state, progress_parameter):
            solutions.append(capture_solution(state))
            return
        
        # ════════════════════════════════════════════════════
        # PRUNING (Optional): Early exit if branch is doomed
        # ════════════════════════════════════════════════════
        if cannot_possibly_succeed(state, progress_parameter):
            return  # Prune this branch
        
        # ════════════════════════════════════════════════════
        # ENUMERATE CANDIDATES: What choices are available?
        # ════════════════════════════════════════════════════
        candidates = get_candidates(state, progress_parameter)
        
        # ════════════════════════════════════════════════════
        # MAIN LOOP: Try each candidate
        # ════════════════════════════════════════════════════
        for candidate in candidates:
            
            # Optional: Skip invalid candidates (lazy filtering)
            if not is_valid(state, candidate):
                continue
            
            # ═══════════ CHOOSE ═══════════
            apply_choice(state, candidate)
            
            # ═══════════ EXPLORE ═══════════
            backtrack(next_progress_parameter)
            
            # ═══════════ UNCHOOSE ═══════════
            undo_choice(state, candidate)
    
    # Initiate the search
    backtrack(initial_progress)
    return solutions

Template Components Explained

State: The current partial solution and any tracking structures.

Progress Parameter: Indicates how close we are to completion (index, remaining value, etc.).

is_complete(): Determines when we've made all decisions — triggers solution capture.

get_candidates(): Enumerates valid choices at the current decision point.

apply_choice() / undo_choice(): Symmetric operations that modify and restore state.

Pruning: Optional early termination when success is impossible.

Recognizing Backtracking Problems

Not every problem calls for backtracking. Knowing when to apply the template is as important as knowing how. Look for these signatures:

Indicators That Backtracking Applies

"Find all combinations/permutations/subsets..." — Explicit enumeration of possibilities
"Count the number of ways to..." — Often solved by backtracking (or DP for efficiency)
"Check if there exists..." — Search for a satisfying assignment
"Solve the puzzle / Satisfy constraints..." — Constraint satisfaction problems
"Generate all valid..." — Exhaustive generation with filtering

Problem Types and Their Backtracking Fit
Problem Type	Backtracking Fit	Reasoning
Generate all permutations	Excellent	Need to enumerate all orderings
Generate all subsets	Excellent	Need to enumerate all combinations
N-Queens	Excellent	Constraint satisfaction + enumeration
Sudoku Solver	Excellent	Constraint satisfaction
Word Search in Grid	Excellent	Path exploration with backtracking
Find shortest path	Poor — Use BFS/Dijkstra	No need for exhaustive search
Maximum subarray sum	Poor — Use Kadane's	Optimal substructure, no branching
Minimum coins (DP))	Can work, but DP better	Overlapping subproblems favor DP
Graph coloring	Good	Assignment with constraints
Traveling Salesman (small n)	Acceptable	Exhaustive but exponential

The Decision Tree Test

Ask yourself: "Can I model this problem as a sequence of decisions, where each decision branches into multiple choices?"

If yes, and the number of decisions is small enough that exhaustive search is feasible, backtracking is likely appropriate.

If the decision tree has overlapping subproblems, consider DP instead. If you need only the optimal path (not all paths), consider greedy or graph algorithms.

Problem-to-Template Mapping

Mapping a problem to the template involves answering six key questions:

What is the state? — What data structures track the partial solution?
What is the progress parameter? — How do we measure progress toward completion?
What is a complete solution? — When do we stop and record a solution?
What are the candidates at each step? — What choices are available?
How do we choose? — What state changes when we make a choice?
How do we unchoose? — What's the symmetric reversal?

Let's walk through this process for several classic problems:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"""
PROBLEM: Generate all subsets of [1, 2, 3]
 
MAPPING:
1. State: current subset being built (list)
2. Progress: current index (0 to n)
3. Complete: index == n (all elements considered)
4. Candidates: {include, exclude} for element at current index
5. Choose: append element to subset
6. Unchoose: pop element from subset
"""
 
def subsets(nums):
    solutions = []
    subset = []  # State
    
    def backtrack(index):  # Progress parameter
        if index == len(nums):  # Complete
            solutions.append(subset[:])
            return
        
        # Candidate 1: Exclude
        backtrack(index + 1)
        
        # Candidate 2: Include
        subset.append(nums[index])  # Choose
        backtrack(index + 1)        # Explore
        subset.pop()                # Unchoose
    
    backtrack(0)
    return solutions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
"""
PROBLEM: Place N queens on NxN board, none attacking each other
 
MAPPING:
1. State: queen positions (list of columns), attack tracking sets
2. Progress: current row (0 to N)
3. Complete: row == N (all queens placed)
4. Candidates: columns not under attack
5. Choose: place queen, mark column/diagonals as attacked
6. Unchoose: remove queen, unmark attacks
"""
 
def solve_n_queens(n):
    solutions = []
    queens = []          # State: column of queen in each row
    cols = set()         # Attacked columns
    diag1 = set()        # Attacked diagonals (r - c)
    diag2 = set()        # Attacked anti-diagonals (r + c)
    
    def backtrack(row):  # Progress parameter
        if row == n:     # Complete
            solutions.append(queens[:])
            return
        
        for col in range(n):  # Candidates: all columns
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue  # Skip attacked columns
            
            # Choose
            queens.append(col)
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            
            backtrack(row + 1)  # Explore
            
            # Unchoose
            diag2.remove(row + col)
            diag1.remove(row - col)
            cols.remove(col)
            queens.pop()
    
    backtrack(0)
    return solutions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
"""
PROBLEM: Find all combinations that sum to target (reuse allowed)
 
MAPPING:
1. State: current combination (list), remaining sum
2. Progress: remaining target (decreases toward 0), start index
3. Complete: remaining == 0
4. Candidates: candidates[start:] with value <= remaining
5. Choose: append candidate, subtract from remaining
6. Unchoose: pop candidate (remaining restored by parameter passing)
"""
 
def combination_sum(candidates, target):
    solutions = []
    combination = []  # State
    
    def backtrack(start, remaining):  # Progress parameters
        if remaining == 0:  # Complete
            solutions.append(combination[:])
            return
        if remaining < 0:   # Pruning
            return
        
        for i in range(start, len(candidates)):
            candidate = candidates[i]
            
            if candidate > remaining:  # Pruning (if sorted)
                continue
            
            combination.append(candidate)           # Choose
            backtrack(i, remaining - candidate)     # Explore (i, not i+1: reuse)
            combination.pop()                       # Unchoose
    
    backtrack(0, target)
    return solutions

Template Variations

The template adapts to different problem requirements. Here are the most common variations:

Variation 1: Find First Solution (Early Termination)

For problems where any valid solution suffices, return immediately upon finding one:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def find_first_solution():
    def backtrack(state):
        if is_complete(state):
            return capture_solution(state)  # Return solution, not append
        
        for candidate in get_candidates(state):
            apply_choice(state, candidate)
            
            result = backtrack(state)
            if result is not None:  # Solution found downstream
                return result       # Propagate upward immediately
            
            undo_choice(state, candidate)
        
        return None  # No solution in this branch
    
    return backtrack(initial_state)

Variation 2: Count Solutions

When you only need the count, not the solutions themselves:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def count_solutions():
    def backtrack(state):
        if is_complete(state):
            return 1  # Found one solution
        
        count = 0
        for candidate in get_candidates(state):
            apply_choice(state, candidate)
            count += backtrack(state)  # Accumulate counts
            undo_choice(state, candidate)
        
        return count
    
    return backtrack(initial_state)

Variation 3: Best Solution (Optimization)

When searching for the optimal (min/max) solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def find_best_solution():
    best = [None]  # Use list for mutability in nested scope
    best_score = [float('inf')]  # Or -inf for maximum
    
    def backtrack(state, current_score):
        if is_complete(state):
            if current_score < best_score[0]:  # New best found
                best[0] = capture_solution(state)
                best_score[0] = current_score
            return
        
        # Pruning: Skip if we can't beat current best
        if current_score + lower_bound_remaining(state) >= best_score[0]:
            return
        
        for candidate in get_candidates(state):
            apply_choice(state, candidate)
            backtrack(state, current_score + cost(candidate))
            undo_choice(state, candidate)
    
    backtrack(initial_state, 0)
    return best[0], best_score[0]

Branch and Bound

The optimization variation often incorporates branch and bound pruning: if the best possible completion of the current path can't beat the best solution found so far, prune immediately. This dramatically reduces search in optimization problems.

Template Customization Patterns

Different problem categories require specific customizations. Here's a catalog of patterns:

Customization Patterns by Problem Type
Problem Type	Key Customization	Example
Subsets/Combinations	Use start index to avoid duplicates; include/exclude each element	Subsets, combination sum
Permutations	Use 'used' boolean array; all unused elements are candidates	Permutations, letter arrangements
With Duplicates	Sort input; skip adjacent duplicates at same level	Permutations II, Combination Sum II
Grid/Path	Use visited matrix; candidates are adjacent cells	Word search, unique paths with obstacles
Constraint Satisfaction	Use constraint sets; candidates filtered by constraints	N-Queens, Sudoku, graph coloring
Partitioning	Multiple accumulators; balance constraints	Partition equal subset, k buckets
String Building	Build string incrementally; candidates from alphabet or rules	Generate parentheses, letter combinations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def permutations_with_duplicates(nums):
    """
    Generate all unique permutations when input may have duplicates.
    Key: Sort and skip duplicates at the same recursion level.
    """
    solutions = []
    nums.sort()  # Essential for duplicate detection
    used = [False] * len(nums)
    
    def backtrack(path):
        if len(path) == len(nums):
            solutions.append(path[:])
            return
        
        for i in range(len(nums)):
            # Skip already used elements
            if used[i]:
                continue
            
            # CRITICAL: Skip duplicates at same level
            # If nums[i] equals nums[i-1] AND nums[i-1] is NOT used,
            # that means we already explored this value at this level.
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            
            used[i] = True
            path.append(nums[i])
            
            backtrack(path)
            
            path.pop()
            used[i] = False
    
    backtrack([])
    return solutions
 
# Input: [1, 1, 2]
# Output: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]  — No duplicates

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def word_search(board, word):
    """
    Find if word exists in grid by following adjacent cells.
    Pattern: Grid exploration with visited tracking.
    """
    rows, cols = len(board), len(board[0])
    
    def backtrack(r, c, index):
        # Complete: matched entire word
        if index == len(word):
            return True
        
        # Pruning: out of bounds, already visited, or mismatch
        if (r < 0 or r >= rows or 
            c < 0 or c >= cols or
            board[r][c] != word[index]):
            return False
        
        # Choose: mark as visited
        temp = board[r][c]
        board[r][c] = '#'  # Mark visited with special character
        
        # Explore: try all 4 directions
        found = (backtrack(r + 1, c, index + 1) or
                 backtrack(r - 1, c, index + 1) or
                 backtrack(r, c + 1, index + 1) or
                 backtrack(r, c - 1, index + 1))
        
        # Unchoose: restore cell
        board[r][c] = temp
        
        return found
    
    # Try starting from each cell
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == word[0] and backtrack(r, c, 0):
                return True
    return False

The Implementation Checklist

Before submitting any backtracking solution, run through this checklist to catch common issues:

Pre-Submission Checklist

•Base Case: Does is_complete() correctly identify when a solution is found? Does it handle edge cases (empty input, n=0)?
•Solution Capture: Are you copying the solution (list(path) or path[:]) or just storing a reference that will mutate?
•Candidates: Are all valid candidates enumerated? Are no invalid candidates included?
•Choose Completeness: Does apply_choice() update ALL relevant state (partial solution, tracking sets, etc.)?
•Unchoose Symmetry: Does undo_choice() reverse EVERY action from apply_choice()?
•Progress Guarantee: Does every recursive call make progress toward the base case (index increases, remaining decreases, etc.)?
•Duplicate Handling: If duplicates in input are possible, are they handled correctly (sort + skip pattern)?
•Pruning (Optional): Are there opportunities for early termination that you're not exploiting?
•Return Value: For first-solution variants, are success values propagated correctly up the call stack?
•Edge Cases: Empty input, single element, all elements identical, no valid solution — do they all work?

Test Incrementally

Don't write the entire solution and hope it works. Test incrementally:

First, verify the base case returns correctly for the simplest inputs.
Then, verify candidate enumeration is correct (print candidates).
Next, verify Choose and Unchoose maintain state correctly (use snapshots).
Finally, test with full examples and edge cases.

Time and Space Complexity

Backtracking algorithms typically have exponential or factorial complexity. Understanding this helps set expectations and identify when pruning is essential.

Complexity of Common Backtracking Problems
Problem	Time Complexity	Space Complexity	Notes
Subsets	O(2ⁿ)	O(n) recursion + O(2ⁿ) output	2ⁿ subsets total
Permutations	O(n!)	O(n) recursion + O(n! × n) output	n! arrangements
Combinations (n choose k)	O(C(n,k) × k)	O(k) recursion + output	C(n,k) combinations
N-Queens	O(n!)	O(n) recursion + board	Heavily pruned in practice
Sudoku	O(9^81) worst	O(81) recursion	Pruning critical; usually fast
Combination Sum	O(n^(T/min))	O(T/min) recursion	T = target, min = smallest candidate

Understanding the Bounds

Time Complexity: Generally proportional to the number of nodes in the solution tree. Each node involves O(candidates) work to enumerate and filter.

Space Complexity: Determined by:

Recursion depth: How many decisions deep can we go?
State storage: Size of tracking structures at each level
Output storage: Total size of all solutions captured

The Pruning Dividend

Pruning doesn't change worst-case complexity (a worst-case input may not be prunable), but it dramatically reduces average-case performance. Good pruning can turn an intractable problem into a millisecond computation.

Know Your Limits

Rough feasibility limits (1 second time limit):

• O(2ⁿ): n ≤ 20-25 • O(n!): n ≤ 10-11 • O(n^n): n ≤ 7-8

If your problem size exceeds these limits and pruning won't help enough, consider DP, memoization, or polynomial algorithms instead of pure backtracking.

Complete Example: Letter Combinations of Phone Number

Let's apply the template end-to-end for a classic problem: given a digit string (e.g., "23"), return all possible letter combinations that the number could represent (like T9 texting).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
def letter_combinations(digits: str) -> list[str]:
    """
    Given a string of digits 2-9, return all letter combinations.
    
    Template Mapping:
    1. State: current combination string being built
    2. Progress: current index in digits string
    3. Complete: index == len(digits)
    4. Candidates: letters corresponding to digits[index]
    5. Choose: append letter to combination
    6. Unchoose: remove last letter from combination
    """
    if not digits:
        return []
    
    # Digit to letters mapping
    digit_to_letters = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    
    solutions = []
    combination = []  # State: current letter combination
    
    def backtrack(index):
        # ════════════════════════════════════
        # BASE CASE: All digits processed
        # ════════════════════════════════════
        if index == len(digits):
            solutions.append(''.join(combination))
            return
        
        # ════════════════════════════════════
        # ENUMERATE CANDIDATES
        # ════════════════════════════════════
        current_digit = digits[index]
        candidates = digit_to_letters[current_digit]
        
        # ════════════════════════════════════
        # MAIN LOOP: Try each letter
        # ════════════════════════════════════
        for letter in candidates:
            # ═══════════ CHOOSE ═══════════
            combination.append(letter)
            
            # ═══════════ EXPLORE ═══════════
            backtrack(index + 1)
            
            # ═══════════ UNCHOOSE ═══════════
            combination.pop()
    
    backtrack(0)
    return solutions
 
# Example:
# Input: "23"
# Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
 
# Analysis:
# - Time: O(4^n × n) where n = len(digits), 4 = max letters per digit
# - Space: O(n) recursion depth + O(4^n × n) output storage

Template in Action

Notice how cleanly the problem maps onto the template:

• State: combination list • Progress: index into digits • Base case: index == len(digits) • Candidates: digit_to_letters[current_digit] • Choose/Unchoose: append / pop

Once you identify these mappings, the code writes itself.

Summary: The Universal Template Mastered

You now possess the complete backtracking template — a versatile tool for solving a wide range of exploratory problems. The template's power lies in its universality: once internalized, you can apply it to any problem that fits the pattern.

Key Takeaways

•The template has three phases: Choose (commit to a candidate), Explore (recurse), Unchoose (restore state).
•Recognize backtracking problems by their signature: enumeration, constraint satisfaction, or existence search.
•Map problems to template by answering six questions: state, progress, completion, candidates, choose, unchoose.
•Apply variations for find-first, count-only, or optimization objectives.
•Customize for problem type: use patterns for duplicates, grids, constraints, partitioning.
•Use the checklist before submission to catch common bugs.
•Understand complexity: exponential/factorial is typical; pruning improves average case.
•Practice mapping until the template becomes second nature.

What's Next:

With the template mastered, you're ready to apply it to specific problem families. The next modules will dive into:

• Subsets & Subsequences — Powerset generation and constrained selection • Permutations & Combinations — Arrangement and selection problems • N-Queens — The canonical constraint satisfaction problem • Sudoku Solver — Complex constraint propagation

Each module will show how the universal template adapts to different problem semantics.

Module Complete

Congratulations! You've completed the Backtracking Template module. You understand Choose, Explore, and Unchoose in depth, and you can apply the universal template to a wide variety of problems. This foundation will serve you well as you tackle increasingly complex backtracking challenges.