Data Structures & AlgorithmsThe Backtracking Template

The Backtracking Template — Choose, Explore, Unchoose

LevelIntermediate

Duration75 mins

TopicThe Backtracking Template

1 / 4

Choose — Make a Decision

The First Step of Systematic Exploration

Every backtracking algorithm begins with a fundamental question: What decision am I making right now?

This deceptively simple question lies at the heart of the backtracking paradigm. Before you can explore possibilities, before you can backtrack from dead ends, you must first make a choice. This choice — the act of selecting one option from a set of candidates — is the Choose phase of the backtracking template.

In this page, we will dissect the Choose phase with surgical precision. You'll learn not just what it means to choose, but how to model decisions effectively, when to apply constraints during selection, and why the order of choices can dramatically affect algorithm performance.

What You Will Learn

By the end of this page, you will understand:

• The conceptual foundations of decision-making in backtracking • How to identify and enumerate candidate choices for any problem • The difference between eager and lazy constraint checking • Why choice ordering affects pruning efficiency • How to implement the Choose phase correctly and robustly

This forms the essential first pillar of the universal backtracking template.

Understanding the Choose Phase

At each step of a backtracking algorithm, you stand at a decision point. Think of it as a junction in a maze: you must decide which path to take. The Choose phase is where you:

Identify the current decision to be made — What variable or position are you filling?
Enumerate all candidates — What are the possible values or options?
Select a candidate — Which one will you try first?
Commit to the choice — Record the decision so it affects subsequent decisions.

This four-part structure applies universally, whether you're placing queens on a chessboard, generating permutations, solving Sudoku, or partitioning strings into palindromes.

The Decision Variable

Every backtracking problem has one or more decision variables — the quantities whose values you're determining. In the N-Queens problem, the decision variable at step i is 'which column does queen i occupy?' In permutation generation, it's 'which unused element goes in position i?' Identifying your decision variable is the first step to implementing Choose correctly.

The Anatomy of a Decision Point

Let's formalize what happens at a decision point:

State before choosing:

You have a partial solution S built from previous choices
You have a set of available candidates C for the current decision
You may have constraints K that restrict valid combinations

The Choose action:

Select one candidate c ∈ C
Add c to the partial solution: S' = S ∪ {c}
Update any tracking structures to reflect that c is now used

State after choosing:

The partial solution has grown by one decision
The available candidates for future decisions may have changed
You're ready to Explore (recurse) with the updated state

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# The Choose phase in abstract form
def backtrack(partial_solution, candidates, ...):
    if is_complete(partial_solution):
        process_solution(partial_solution)
        return
    
    # CHOOSE PHASE: iterate through candidate choices
    for choice in get_candidates(partial_solution, candidates):
        # Make the choice
        partial_solution.add(choice)
        update_tracking_structures(choice)
        
        # EXPLORE PHASE: recurse with the choice made
        backtrack(partial_solution, updated_candidates, ...)
        
        # UNCHOOSE PHASE: undo the choice
        partial_solution.remove(choice)
        restore_tracking_structures(choice)

Modeling Decisions Effectively

The way you model your decisions profoundly affects both the correctness and efficiency of your backtracking algorithm. Poor modeling leads to duplicate solutions, missed solutions, or exponentially larger search spaces. Effective modeling creates a clean, systematic exploration.

The Key Principle: One Decision, One Axis of Freedom

At each recursion level, you should be making exactly one well-defined decision. If your decision involves multiple independent choices, you're likely modeling incorrectly — either you'll generate duplicates or miss valid solutions.

Poor Decision Modeling

•Deciding 'which subset to generate' at each level
•Choosing 'which elements to include' as a group
•Making multiple placements in one recursive call
•Jumping to random parts of the solution
•Mixing different types of decisions

Effective Decision Modeling

•Deciding 'include or exclude element i' at each level
•Choosing 'which single element fills position i'
•One placement per recursive call
•Processing positions/elements in a fixed order
•Homogeneous decisions throughout

Example: Two Ways to Model Subset Generation

Consider generating all subsets of {1, 2, 3}. There are two fundamentally different ways to model the decisions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def subsets_include_exclude(nums):
    """
    Decision model: At position i, decide to INCLUDE or EXCLUDE nums[i].
    Each decision is binary, leading to exactly 2^n leaves.
    """
    result = []
    
    def backtrack(index, current):
        if index == len(nums):
            result.append(current[:])  # Base case: all decisions made
            return
        
        # Choice 1: EXCLUDE nums[index]
        backtrack(index + 1, current)
        
        # Choice 2: INCLUDE nums[index]
        current.append(nums[index])      # Choose
        backtrack(index + 1, current)     # Explore
        current.pop()                     # Unchoose
    
    backtrack(0, [])
    return result
 
# Output: [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def subsets_choose_next(nums):
    """
    Decision model: At each step, choose which element to add next.
    Use a start index to avoid duplicates and maintain order.
    """
    result = []
    
    def backtrack(start, current):
        result.append(current[:])  # Every partial solution is valid
        
        for i in range(start, len(nums)):
            current.append(nums[i])      # Choose
            backtrack(i + 1, current)    # Explore (start from i+1, not 0)
            current.pop()                # Unchoose
    
    backtrack(0, [])
    return result
 
# Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Both Models Are Valid

Both approaches generate the same subsets (in different orders). Model A makes exactly n decisions (one per element), resulting in exactly 2^n recursive leaves. Model B has a different structure: each call may make 0 to (n-start) choices, but the total work is still O(2^n). Choose the model that best matches your intuition and problem constraints.

Enumerating Candidates

Once you've identified what decision you're making, you need to enumerate all valid candidates for that decision. This enumeration is critical: missing a candidate means missing solutions; including invalid candidates wastes computation.

The Candidate Set

The candidate set at any decision point depends on:

The problem domain — What are the theoretically possible values?
Global constraints — What values are fundamentally forbidden?
Current state — What choices have already been made?
Local constraints — What's valid given the current partial solution?

The candidate set is the intersection of all these considerations.

Candidate Sets Across Classic Problems
Problem	Decision	Full Domain	Candidates at Step i
N-Queens	Column for queen i	Columns 0 to N-1	Columns not attacked by queens 0..i-1
Permutations	Element for position i	All elements	Elements not yet used
Subsets	Include element i?	{true, false}	Always both (no filtering needed)
Sudoku	Value for cell (r,c)	Digits 1-9	Digits not in row, column, or box
Combination Sum	Next element to add	All elements	Elements with value ≤ remaining target

Lazy vs. Eager Candidate Filtering

You have two strategies for handling constraints during candidate enumeration:

Eager Filtering (Filter Before Loop):

Compute the valid candidate set before iterating
Only iterate through candidates that are definitely valid
More work upfront, but fewer wasted iterations

Lazy Filtering (Check Inside Loop):

Iterate through all possible candidates
Check validity inside the loop before making the choice
Simpler code, but may iterate through many invalid candidates

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
# EAGER FILTERING: Pre-compute valid columns
def solve_n_queens_eager(n):
    result = []
    
    def get_valid_columns(queens, row):
        """Returns set of valid columns for queen at 'row'."""
        valid = set(range(n))
        for r, c in enumerate(queens):
            valid.discard(c)                    # Same column
            valid.discard(c + (row - r))        # Diagonal
            valid.discard(c - (row - r))        # Anti-diagonal
        return valid
    
    def backtrack(queens):
        row = len(queens)
        if row == n:
            result.append(queens[:])
            return
        
        for col in get_valid_columns(queens, row):  # Only valid candidates
            queens.append(col)
            backtrack(queens)
            queens.pop()
    
    backtrack([])
    return result
 
# LAZY FILTERING: Check validity inside loop
def solve_n_queens_lazy(n):
    result = []
    
    def is_valid(queens, row, col):
        """Check if placing queen at (row, col) is valid."""
        for r, c in enumerate(queens):
            if c == col:                        # Same column
                return False
            if abs(row - r) == abs(col - c):    # Diagonal
                return False
        return True
    
    def backtrack(queens):
        row = len(queens)
        if row == n:
            result.append(queens[:])
            return
        
        for col in range(n):                    # All columns
            if is_valid(queens, row, col):      # Filter inside loop
                queens.append(col)
                backtrack(queens)
                queens.pop()
    
    backtrack([])
    return result

When to Use Each Approach

Eager filtering is better when: • Computing the valid set is cheap • Many candidates are invalid (high rejection rate) • The validity check is expensive

Lazy filtering is better when: • Most candidates are valid • The full candidate set is small • Code simplicity is prioritized

The Art of Choice Ordering

A subtle but powerful insight: the order in which you try candidates can dramatically affect performance. While any order will eventually find all solutions (for generation problems) or find a solution if one exists (for search problems), the order affects how much of the search tree you explore before succeeding or pruning.

Fail-Fast Principle

If you're searching for any valid solution, order candidates so that:

More constrained choices come first — They fail faster if invalid
More likely candidates come first — They succeed faster if valid

This heuristic is called fail-fast or most-constrained-first ordering.

Example: Sudoku with Intelligent Cell Ordering

In Sudoku, you can process cells in any order (left-to-right, top-to-bottom), but a smarter approach is to always choose the Most Constrained Variable (MCV) — the cell with the fewest valid candidates.

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
def solve_sudoku_mcv(board):
    """
    Sudoku solver using Most Constrained Variable heuristic.
    Always chooses the empty cell with fewest valid candidates.
    """
    def get_candidates(board, row, col):
        """Returns valid digits for cell (row, col)."""
        candidates = set(range(1, 10))
        
        # Remove digits in same row
        candidates -= set(board[row])
        
        # Remove digits in same column
        candidates -= {board[r][col] for r in range(9)}
        
        # Remove digits in same 3x3 box
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for r in range(box_row, box_row + 3):
            for c in range(box_col, box_col + 3):
                candidates.discard(board[r][c])
        
        return candidates
    
    def find_most_constrained_cell(board):
        """Find empty cell with minimum candidates (MCV heuristic)."""
        min_candidates = 10
        best_cell = None
        
        for row in range(9):
            for col in range(9):
                if board[row][col] == 0:  # Empty cell
                    candidates = get_candidates(board, row, col)
                    if len(candidates) < min_candidates:
                        min_candidates = len(candidates)
                        best_cell = (row, col, candidates)
                        if min_candidates == 1:  # Can't do better
                            return best_cell
        
        return best_cell
    
    def backtrack():
        cell = find_most_constrained_cell(board)
        if cell is None:
            return True  # All cells filled — solution found!
        
        row, col, candidates = cell
        
        if not candidates:
            return False  # No candidates — backtrack!
        
        for digit in candidates:
            board[row][col] = digit       # Choose
            if backtrack():               # Explore
                return True
            board[row][col] = 0           # Unchoose
        
        return False
    
    backtrack()
    return board

The Power of MCV

The MCV heuristic can reduce Sudoku solving from thousands of backtracks to just a few dozen. By always choosing the cell with the fewest options, you:

• Detect failures earlier (a cell with 0 candidates means immediate backtrack) • Make forced moves instantly (cells with 1 candidate have no choice) • Keep the branching factor low throughout the search

Value Ordering: Least Constraining Value

Beyond choosing which variable to decide, you can also order the values you try for that variable. The Least Constraining Value (LCV) heuristic suggests trying values that leave the most options open for future variables.

This is the opposite intuition from MCV:

MCV (for variables): Choose the most constrained first to fail fast
LCV (for values): Choose the least constraining first to succeed fast

Variable vs. Value Ordering Heuristics
Heuristic	Applies To	Strategy	Goal
MCV/MRV	Which variable (cell) to fill next	Choose variable with fewest options	Fail fast on dead ends
LCV	Which value to try first for a variable	Choose value that constrains future variables least	Succeed fast on solvable branches
Degree	Which variable to fill next	Choose variable involved in most constraints	Maximize pruning impact

Committing to the Choice

Making a choice isn't just deciding — it's recording that decision so it influences all subsequent decisions. This commitment typically involves:

Adding to the partial solution — Append to a list, set a cell value, etc.
Updating tracking structures — Mark elements as used, update constraint sets
Potentially updating the candidate sets — Reduce options for future decisions

The key principle: after committing, the algorithm state must fully reflect that the choice has been made.

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
def generate_permutations(nums):
    """
    Generate all permutations of nums.
    Demonstrates proper commitment and state tracking.
    """
    result = []
    n = len(nums)
    used = [False] * n  # Tracking structure for used elements
    
    def backtrack(current_permutation):
        if len(current_permutation) == n:
            result.append(current_permutation[:])
            return
        
        for i in range(n):
            if used[i]:  # Skip already-used elements
                continue
            
            # === COMMIT TO THE CHOICE ===
            current_permutation.append(nums[i])  # 1. Add to partial solution
            used[i] = True                       # 2. Update tracking structure
            
            # === EXPLORE ===
            backtrack(current_permutation)
            
            # === UNDO THE COMMITMENT (Unchoose) ===
            current_permutation.pop()            # 1. Remove from partial solution
            used[i] = False                      # 2. Restore tracking structure
    
    backtrack([])
    return result

Tracking Structures: The Memory of Your Choices

Tracking structures are auxiliary data structures that remember which choices have been made. They enable O(1) queries like "Is element X already used?" or "Is column C under attack?"

Common tracking structures include:

Common Tracking Structures in Backtracking
Structure	Purpose	Example Usage
Boolean array `used[i]`	Track which elements are in current solution	Permutations: which numbers are placed
Set `used_set`	O(1) membership check for used items	Letter Tiles: which letters are used
Column set `cols`	Track attacked columns	N-Queens: columns with queens
Diagonal sets `diag1`, `diag2`	Track attacked diagonals	N-Queens: diagonal indices
Remaining capacity	Track remaining resource	Knapsack/Combination Sum: remaining target
Current position/index	Track progress through input	Subsets: which element to consider next

Consistency is Crucial

Every update made during the Choose phase MUST be undone during the Unchoose phase. If you add to a set during Choose, you must remove during Unchoose. If you set used[i] = True, you must set used[i] = False. Any inconsistency leads to incorrect results or missed solutions.

Common Pitfalls in the Choose Phase

The Choose phase is where most backtracking bugs originate. Understanding common pitfalls helps you write correct code from the start.

Common Pitfalls and Fixes

•Generating Duplicates: If your problem requires unique combinations, ensure your decision model doesn't visit the same combination twice. Fix: Use a start index that only looks forward, or skip duplicate adjacent elements after sorting.
•Missing Solutions: Failing to enumerate all candidates, or over-aggressive constraint checking that rejects valid options. Fix: Carefully verify your candidate generation covers all valid choices.
•Infinite Loops: If the decision doesn't reduce the problem size, recursion never terminates. Fix: Ensure each recursive call makes progress toward the base case.
•Wrong State After Unchoose: Forgetting to undo all tracking updates leads to corrupted state. Fix: Pair every Choose action with an equal-and-opposite Unchoose action.
•Shallow Copy vs. Deep Copy: Adding current_list to results without copying means all results point to the same mutated list. Fix: Use result.append(current[:]) or result.append(list(current)).

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
def combination_sum_2(candidates, target):
    """
    Find all unique combinations that sum to target.
    Each candidate can be used only once.
    Candidates may contain duplicates.
    """
    result = []
    candidates.sort()  # Sort to handle duplicates
    
    def backtrack(start, target, path):
        if target == 0:
            result.append(path[:])
            return
        if target < 0:
            return
        
        for i in range(start, len(candidates)):
            # CRITICAL: Skip duplicates at the same level of recursion
            if i > start and candidates[i] == candidates[i - 1]:
                continue  # Skip duplicate candidates
            
            path.append(candidates[i])           # Choose
            backtrack(i + 1, target - candidates[i], path)  # Explore
            path.pop()                           # Unchoose
    
    backtrack(0, target, [])
    return result
 
# Example: candidates = [10,1,2,7,6,1,5], target = 8
# Output: [[1,1,6], [1,2,5], [1,7], [2,6]]
# Note: No duplicate combinations like [1,7] appearing twice

The Duplicate-Skipping Pattern

The pattern if i > start and candidates[i] == candidates[i-1]: continue is essential when dealing with duplicate elements. It ensures that duplicate elements are only used together in combinations (not at the same recursion level), preventing duplicate solutions while still allowing valid combinations that use multiple copies of the same value.

Choose Phase Across Problem Types

Let's see how the Choose phase manifests across different categories of backtracking problems. Recognizing these patterns will help you quickly structure solutions for new problems.

Choose Phase Patterns by Problem Type
Problem Type	Decision Variable	Candidates	Commit Action
Subsets/Combinations	Include element at index i?	{include, exclude}	Add element to current subset
Permutations	Which element fills position i?	All unused elements	Add element, mark as used
N-Queens	Which column for queen in row i?	Safe columns	Record column, update attack sets
Sudoku	Which digit for cell (r, c)?	Digits not violating constraints	Set cell value
Graph Coloring	Which color for vertex v?	Colors not used by neighbors	Assign color to vertex
Maze/Path Finding	Which direction to move?	Valid adjacent cells	Update current position
Word Break	What is the next word in segmentation?	Valid dictionary words starting at current position	Record word, advance position

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
def word_break_all_solutions(s, word_dict):
    """
    Find all ways to segment string s into dictionary words.
    Returns all valid segmentations.
    """
    result = []
    word_set = set(word_dict)
    
    def backtrack(start, path):
        if start == len(s):
            result.append(' '.join(path))
            return
        
        # CHOOSE: Try each possible word starting at 'start'
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            
            if word in word_set:  # Valid candidate
                path.append(word)              # Commit: add word to segmentation
                backtrack(end, path)           # Explore: continue from next position
                path.pop()                     # Unchoose: remove word
    
    backtrack(0, [])
    return result
 
# Example: s = "catsanddog", word_dict = ["cat","cats","and","sand","dog"]
# Output: ["cats and dog", "cat sand dog"]

Summary: Mastering the Choose Phase

The Choose phase is where exploration begins. Every path through the solution space starts with a choice, and the quality of your choice implementation determines both correctness and efficiency.

Key Takeaways

•Identify your decision variable — Know exactly what you're deciding at each step before writing any code.
•Model decisions as atomic units — Each recursion level should make exactly one well-defined choice.
•Enumerate candidates correctly — Your candidate set must include all valid options and exclude all invalid ones.
•Consider eager vs. lazy filtering — Pre-compute valid candidates when filtering is cheap and rejection rate is high.
•Order choices strategically — Use MCV for variable ordering and LCV for value ordering to prune the search space.
•Commit fully — Update all tracking structures when making a choice; you'll undo them all during Unchoose.
•Avoid common pitfalls — Watch for duplicates, missed solutions, and copy issues.

What's Next:

With the Choose phase understood, we'll explore the Explore phase — where recursion deepens the search. You'll learn how recursive calls propagate choices through the solution space, how to structure base cases correctly, and how the exploration phase connects Choose and Unchoose into a complete backtracking loop.

Page Complete

You now understand the Choose phase of the backtracking template in depth. You know how to identify decisions, enumerate candidates, apply ordering heuristics, and commit to choices correctly. This foundation prepares you for the Explore and Unchoose phases that complete the template.

1 / 4

Loading learning content...

Data Structures & AlgorithmsThe Backtracking Template

The Backtracking Template — Choose, Explore, Unchoose

LevelIntermediate

Duration75 mins

TopicThe Backtracking Template

1 / 4

Choose — Make a Decision

The First Step of Systematic Exploration

Every backtracking algorithm begins with a fundamental question: What decision am I making right now?

What You Will Learn

By the end of this page, you will understand:

This forms the essential first pillar of the universal backtracking template.

Understanding the Choose Phase

At each step of a backtracking algorithm, you stand at a decision point. Think of it as a junction in a maze: you must decide which path to take. The Choose phase is where you:

Identify the current decision to be made — What variable or position are you filling?
Enumerate all candidates — What are the possible values or options?
Select a candidate — Which one will you try first?
Commit to the choice — Record the decision so it affects subsequent decisions.

This four-part structure applies universally, whether you're placing queens on a chessboard, generating permutations, solving Sudoku, or partitioning strings into palindromes.

The Decision Variable

The Anatomy of a Decision Point

Let's formalize what happens at a decision point:

State before choosing:

You have a partial solution S built from previous choices
You have a set of available candidates C for the current decision
You may have constraints K that restrict valid combinations

The Choose action:

Select one candidate c ∈ C
Add c to the partial solution: S' = S ∪ {c}
Update any tracking structures to reflect that c is now used

State after choosing:

The partial solution has grown by one decision
The available candidates for future decisions may have changed
You're ready to Explore (recurse) with the updated state

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# The Choose phase in abstract form
def backtrack(partial_solution, candidates, ...):
    if is_complete(partial_solution):
        process_solution(partial_solution)
        return
    
    # CHOOSE PHASE: iterate through candidate choices
    for choice in get_candidates(partial_solution, candidates):
        # Make the choice
        partial_solution.add(choice)
        update_tracking_structures(choice)
        
        # EXPLORE PHASE: recurse with the choice made
        backtrack(partial_solution, updated_candidates, ...)
        
        # UNCHOOSE PHASE: undo the choice
        partial_solution.remove(choice)
        restore_tracking_structures(choice)

Modeling Decisions Effectively

The Key Principle: One Decision, One Axis of Freedom

Poor Decision Modeling

•Deciding 'which subset to generate' at each level
•Choosing 'which elements to include' as a group
•Making multiple placements in one recursive call
•Jumping to random parts of the solution
•Mixing different types of decisions

Effective Decision Modeling

•Deciding 'include or exclude element i' at each level
•Choosing 'which single element fills position i'
•One placement per recursive call
•Processing positions/elements in a fixed order
•Homogeneous decisions throughout

Example: Two Ways to Model Subset Generation

Consider generating all subsets of {1, 2, 3}. There are two fundamentally different ways to model the decisions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def subsets_include_exclude(nums):
    """
    Decision model: At position i, decide to INCLUDE or EXCLUDE nums[i].
    Each decision is binary, leading to exactly 2^n leaves.
    """
    result = []
    
    def backtrack(index, current):
        if index == len(nums):
            result.append(current[:])  # Base case: all decisions made
            return
        
        # Choice 1: EXCLUDE nums[index]
        backtrack(index + 1, current)
        
        # Choice 2: INCLUDE nums[index]
        current.append(nums[index])      # Choose
        backtrack(index + 1, current)     # Explore
        current.pop()                     # Unchoose
    
    backtrack(0, [])
    return result
 
# Output: [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def subsets_choose_next(nums):
    """
    Decision model: At each step, choose which element to add next.
    Use a start index to avoid duplicates and maintain order.
    """
    result = []
    
    def backtrack(start, current):
        result.append(current[:])  # Every partial solution is valid
        
        for i in range(start, len(nums)):
            current.append(nums[i])      # Choose
            backtrack(i + 1, current)    # Explore (start from i+1, not 0)
            current.pop()                # Unchoose
    
    backtrack(0, [])
    return result
 
# Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Both Models Are Valid

Enumerating Candidates

The Candidate Set

The candidate set at any decision point depends on:

The problem domain — What are the theoretically possible values?
Global constraints — What values are fundamentally forbidden?
Current state — What choices have already been made?
Local constraints — What's valid given the current partial solution?

The candidate set is the intersection of all these considerations.

Candidate Sets Across Classic Problems
Problem	Decision	Full Domain	Candidates at Step i
N-Queens	Column for queen i	Columns 0 to N-1	Columns not attacked by queens 0..i-1
Permutations	Element for position i	All elements	Elements not yet used
Subsets	Include element i?	{true, false}	Always both (no filtering needed)
Sudoku	Value for cell (r,c)	Digits 1-9	Digits not in row, column, or box
Combination Sum	Next element to add	All elements	Elements with value ≤ remaining target

Lazy vs. Eager Candidate Filtering

You have two strategies for handling constraints during candidate enumeration:

Eager Filtering (Filter Before Loop):

Compute the valid candidate set before iterating
Only iterate through candidates that are definitely valid
More work upfront, but fewer wasted iterations

Lazy Filtering (Check Inside Loop):

Iterate through all possible candidates
Check validity inside the loop before making the choice
Simpler code, but may iterate through many invalid candidates

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
# EAGER FILTERING: Pre-compute valid columns
def solve_n_queens_eager(n):
    result = []
    
    def get_valid_columns(queens, row):
        """Returns set of valid columns for queen at 'row'."""
        valid = set(range(n))
        for r, c in enumerate(queens):
            valid.discard(c)                    # Same column
            valid.discard(c + (row - r))        # Diagonal
            valid.discard(c - (row - r))        # Anti-diagonal
        return valid
    
    def backtrack(queens):
        row = len(queens)
        if row == n:
            result.append(queens[:])
            return
        
        for col in get_valid_columns(queens, row):  # Only valid candidates
            queens.append(col)
            backtrack(queens)
            queens.pop()
    
    backtrack([])
    return result
 
# LAZY FILTERING: Check validity inside loop
def solve_n_queens_lazy(n):
    result = []
    
    def is_valid(queens, row, col):
        """Check if placing queen at (row, col) is valid."""
        for r, c in enumerate(queens):
            if c == col:                        # Same column
                return False
            if abs(row - r) == abs(col - c):    # Diagonal
                return False
        return True
    
    def backtrack(queens):
        row = len(queens)
        if row == n:
            result.append(queens[:])
            return
        
        for col in range(n):                    # All columns
            if is_valid(queens, row, col):      # Filter inside loop
                queens.append(col)
                backtrack(queens)
                queens.pop()
    
    backtrack([])
    return result

When to Use Each Approach

Eager filtering is better when: • Computing the valid set is cheap • Many candidates are invalid (high rejection rate) • The validity check is expensive

Lazy filtering is better when: • Most candidates are valid • The full candidate set is small • Code simplicity is prioritized

The Art of Choice Ordering

Fail-Fast Principle

If you're searching for any valid solution, order candidates so that:

More constrained choices come first — They fail faster if invalid
More likely candidates come first — They succeed faster if valid

This heuristic is called fail-fast or most-constrained-first ordering.

Example: Sudoku with Intelligent Cell Ordering

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
def solve_sudoku_mcv(board):
    """
    Sudoku solver using Most Constrained Variable heuristic.
    Always chooses the empty cell with fewest valid candidates.
    """
    def get_candidates(board, row, col):
        """Returns valid digits for cell (row, col)."""
        candidates = set(range(1, 10))
        
        # Remove digits in same row
        candidates -= set(board[row])
        
        # Remove digits in same column
        candidates -= {board[r][col] for r in range(9)}
        
        # Remove digits in same 3x3 box
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for r in range(box_row, box_row + 3):
            for c in range(box_col, box_col + 3):
                candidates.discard(board[r][c])
        
        return candidates
    
    def find_most_constrained_cell(board):
        """Find empty cell with minimum candidates (MCV heuristic)."""
        min_candidates = 10
        best_cell = None
        
        for row in range(9):
            for col in range(9):
                if board[row][col] == 0:  # Empty cell
                    candidates = get_candidates(board, row, col)
                    if len(candidates) < min_candidates:
                        min_candidates = len(candidates)
                        best_cell = (row, col, candidates)
                        if min_candidates == 1:  # Can't do better
                            return best_cell
        
        return best_cell
    
    def backtrack():
        cell = find_most_constrained_cell(board)
        if cell is None:
            return True  # All cells filled — solution found!
        
        row, col, candidates = cell
        
        if not candidates:
            return False  # No candidates — backtrack!
        
        for digit in candidates:
            board[row][col] = digit       # Choose
            if backtrack():               # Explore
                return True
            board[row][col] = 0           # Unchoose
        
        return False
    
    backtrack()
    return board

The Power of MCV

The MCV heuristic can reduce Sudoku solving from thousands of backtracks to just a few dozen. By always choosing the cell with the fewest options, you:

Value Ordering: Least Constraining Value

This is the opposite intuition from MCV:

MCV (for variables): Choose the most constrained first to fail fast
LCV (for values): Choose the least constraining first to succeed fast

Variable vs. Value Ordering Heuristics
Heuristic	Applies To	Strategy	Goal
MCV/MRV	Which variable (cell) to fill next	Choose variable with fewest options	Fail fast on dead ends
LCV	Which value to try first for a variable	Choose value that constrains future variables least	Succeed fast on solvable branches
Degree	Which variable to fill next	Choose variable involved in most constraints	Maximize pruning impact

Committing to the Choice

Making a choice isn't just deciding — it's recording that decision so it influences all subsequent decisions. This commitment typically involves:

Adding to the partial solution — Append to a list, set a cell value, etc.
Updating tracking structures — Mark elements as used, update constraint sets
Potentially updating the candidate sets — Reduce options for future decisions

The key principle: after committing, the algorithm state must fully reflect that the choice has been made.

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
def generate_permutations(nums):
    """
    Generate all permutations of nums.
    Demonstrates proper commitment and state tracking.
    """
    result = []
    n = len(nums)
    used = [False] * n  # Tracking structure for used elements
    
    def backtrack(current_permutation):
        if len(current_permutation) == n:
            result.append(current_permutation[:])
            return
        
        for i in range(n):
            if used[i]:  # Skip already-used elements
                continue
            
            # === COMMIT TO THE CHOICE ===
            current_permutation.append(nums[i])  # 1. Add to partial solution
            used[i] = True                       # 2. Update tracking structure
            
            # === EXPLORE ===
            backtrack(current_permutation)
            
            # === UNDO THE COMMITMENT (Unchoose) ===
            current_permutation.pop()            # 1. Remove from partial solution
            used[i] = False                      # 2. Restore tracking structure
    
    backtrack([])
    return result

Tracking Structures: The Memory of Your Choices

Tracking structures are auxiliary data structures that remember which choices have been made. They enable O(1) queries like "Is element X already used?" or "Is column C under attack?"

Common tracking structures include:

Common Tracking Structures in Backtracking
Structure	Purpose	Example Usage
Boolean array `used[i]`	Track which elements are in current solution	Permutations: which numbers are placed
Set `used_set`	O(1) membership check for used items	Letter Tiles: which letters are used
Column set `cols`	Track attacked columns	N-Queens: columns with queens
Diagonal sets `diag1`, `diag2`	Track attacked diagonals	N-Queens: diagonal indices
Remaining capacity	Track remaining resource	Knapsack/Combination Sum: remaining target
Current position/index	Track progress through input	Subsets: which element to consider next

Consistency is Crucial

Common Pitfalls in the Choose Phase

The Choose phase is where most backtracking bugs originate. Understanding common pitfalls helps you write correct code from the start.

Common Pitfalls and Fixes

•Generating Duplicates: If your problem requires unique combinations, ensure your decision model doesn't visit the same combination twice. Fix: Use a start index that only looks forward, or skip duplicate adjacent elements after sorting.
•Missing Solutions: Failing to enumerate all candidates, or over-aggressive constraint checking that rejects valid options. Fix: Carefully verify your candidate generation covers all valid choices.
•Infinite Loops: If the decision doesn't reduce the problem size, recursion never terminates. Fix: Ensure each recursive call makes progress toward the base case.
•Wrong State After Unchoose: Forgetting to undo all tracking updates leads to corrupted state. Fix: Pair every Choose action with an equal-and-opposite Unchoose action.
•Shallow Copy vs. Deep Copy: Adding current_list to results without copying means all results point to the same mutated list. Fix: Use result.append(current[:]) or result.append(list(current)).

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
def combination_sum_2(candidates, target):
    """
    Find all unique combinations that sum to target.
    Each candidate can be used only once.
    Candidates may contain duplicates.
    """
    result = []
    candidates.sort()  # Sort to handle duplicates
    
    def backtrack(start, target, path):
        if target == 0:
            result.append(path[:])
            return
        if target < 0:
            return
        
        for i in range(start, len(candidates)):
            # CRITICAL: Skip duplicates at the same level of recursion
            if i > start and candidates[i] == candidates[i - 1]:
                continue  # Skip duplicate candidates
            
            path.append(candidates[i])           # Choose
            backtrack(i + 1, target - candidates[i], path)  # Explore
            path.pop()                           # Unchoose
    
    backtrack(0, target, [])
    return result
 
# Example: candidates = [10,1,2,7,6,1,5], target = 8
# Output: [[1,1,6], [1,2,5], [1,7], [2,6]]
# Note: No duplicate combinations like [1,7] appearing twice

The Duplicate-Skipping Pattern

Choose Phase Across Problem Types

Let's see how the Choose phase manifests across different categories of backtracking problems. Recognizing these patterns will help you quickly structure solutions for new problems.

Choose Phase Patterns by Problem Type
Problem Type	Decision Variable	Candidates	Commit Action
Subsets/Combinations	Include element at index i?	{include, exclude}	Add element to current subset
Permutations	Which element fills position i?	All unused elements	Add element, mark as used
N-Queens	Which column for queen in row i?	Safe columns	Record column, update attack sets
Sudoku	Which digit for cell (r, c)?	Digits not violating constraints	Set cell value
Graph Coloring	Which color for vertex v?	Colors not used by neighbors	Assign color to vertex
Maze/Path Finding	Which direction to move?	Valid adjacent cells	Update current position
Word Break	What is the next word in segmentation?	Valid dictionary words starting at current position	Record word, advance position

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
def word_break_all_solutions(s, word_dict):
    """
    Find all ways to segment string s into dictionary words.
    Returns all valid segmentations.
    """
    result = []
    word_set = set(word_dict)
    
    def backtrack(start, path):
        if start == len(s):
            result.append(' '.join(path))
            return
        
        # CHOOSE: Try each possible word starting at 'start'
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            
            if word in word_set:  # Valid candidate
                path.append(word)              # Commit: add word to segmentation
                backtrack(end, path)           # Explore: continue from next position
                path.pop()                     # Unchoose: remove word
    
    backtrack(0, [])
    return result
 
# Example: s = "catsanddog", word_dict = ["cat","cats","and","sand","dog"]
# Output: ["cats and dog", "cat sand dog"]

Summary: Mastering the Choose Phase

The Choose phase is where exploration begins. Every path through the solution space starts with a choice, and the quality of your choice implementation determines both correctness and efficiency.

Key Takeaways

•Identify your decision variable — Know exactly what you're deciding at each step before writing any code.
•Model decisions as atomic units — Each recursion level should make exactly one well-defined choice.
•Enumerate candidates correctly — Your candidate set must include all valid options and exclude all invalid ones.
•Consider eager vs. lazy filtering — Pre-compute valid candidates when filtering is cheap and rejection rate is high.
•Order choices strategically — Use MCV for variable ordering and LCV for value ordering to prune the search space.
•Commit fully — Update all tracking structures when making a choice; you'll undo them all during Unchoose.
•Avoid common pitfalls — Watch for duplicates, missed solutions, and copy issues.

What's Next:

Page Complete

1 / 4