Introduction to Backtracking

This lesson defines backtracking as a systematic search technique, explains the state space tree and the choose → explore → unchoose pattern, contrasts backtracking with DP, greedy, and brute force, introduces pruning, and maps classic backtracking problems to real-world applications.

What is Backtracking?

Backtracking is an algorithmic technique for exploring all (or many) candidates for a solution by building them incrementally. When a partial solution cannot lead to a valid complete solution, the algorithm abandons that branch and returns to a previous decision point—hence “backtrack.”

Backtracking is not one fixed algorithm; it is a problem-solving paradigm built on recursion (or an explicit stack). You maintain a partial solution, try extending it, and undo the last choice when constraints fail or all extensions are exhausted.

Schematic: State space tree for [1, 2, 3] permutations

Each level picks the next element; dead ends are pruned when a choice is invalid:

                    []
           /        |        \
         [1]       [2]       [3]
        /   \     /   \       |
    [1,2] [1,3] [2,1] [2,3] [3,1] ...
      |     |     |     |     |
  [1,2,3] ...  (complete permutations at leaves)

Backtrack: if [1,2] cannot extend → undo 2, try [1,3]

Core Concepts

Every backtracking problem can be described with these building blocks:

1. State

What you track at each step: current path, board configuration, remaining choices, indices, etc.

Examples: list of chosen numbers; N×N chess board; Sudoku grid; maze cell coordinates.

2. Choices

Valid options to extend the partial solution at the current step.

Examples: unused digits; empty cells in a row; four directions in a maze.

3. Constraints

Rules that reject invalid partial solutions early.

Examples: no duplicate permutations; no two queens attack; Sudoku row/column/box uniqueness.

4. Goal / Base Case

When the partial solution is complete and should be recorded (or counted).

Examples: path length equals n; all queens placed; Sudoku grid filled.

The Backtracking Template

The universal pattern is choose → explore → unchoose (also called pick / recurse / unpick):

def backtrack(state):
    if is_complete(state):
        record_solution(state)
        return

    for choice in valid_choices(state):
        if not is_valid(state, choice):
            continue          # prune
        apply(state, choice)  # choose
        backtrack(state)      # explore
        undo(state, choice)   # unchoose (backtrack)

For problems that need all solutions, do not return after finding one—collect every leaf. For “exists?” problems, return early on first success.

Backtracking vs DP vs Greedy vs Brute Force

All can search solution spaces, but commitments and reuse differ:

Quick Comparison Examples

Backtracking — N-Queens:

Place queen row by row; if column/diagonal conflict → backtrack
Try all valid columns per row; collect all board layouts

DP — Coin change (min coins):

Amount 6, coins [1,3,4]
dp[6] = min(dp[5]+1, dp[3]+1, dp[2]+1) — reuse sub-answers
Not generating every coin sequence explicitly

Greedy — Activity selection:

Sort by finish time; pick greedily — no undo, no full tree

Pruning Overview

Pruning skips branches that cannot yield a valid or optimal solution. It is what makes backtracking practical.

• Constraint pruning: Invalid partial state → return immediately (Sudoku duplicate in row).
• Feasibility pruning: Remaining slots cannot satisfy constraints (not enough cells left).
• Bound pruning: In optimization, current cost already exceeds best known (branch-and-bound).

See Pruning techniques for a deeper dive with examples.

When to Use Backtracking

Classic Backtracking Problems

These map to tutorials in this backtracking track:

1. Fundamentals

• Pruning techniques — constraint, feasibility, and bound pruning

2. Board & Grid

• N-Queens — place queens with no mutual attacks
• Sudoku solver — fill grid with row/column/box rules
• Rat in a maze — find path in a grid
• Word search — find dictionary words on a board

3. Combinatorial Generation

• Generate permutations — all orderings of a set
• Generate combinations — all k-subsets

Other Famous Backtracking Problems (reference)

• Subset sum / partition problems
• Graph coloring
• Hamiltonian path
• Knight’s tour
• Word Break II (backtrack on top of DP reachability)

Real-Life Applications

Backtracking models systematic trial with early rejection—common in planning, puzzles, and design tools:

Cross-Domain Examples

• Operations research: Integer programming with branch-and-bound (pruned backtracking)
• Compilers: Parsing and code generation explore alternative productions
• Security: Password / key search in constrained spaces
• Bioinformatics: Sequence alignment variants explore edit paths
• UI testing: Generate interaction sequences covering state spaces

Next Steps

Continue Learning

1. Pruning Techniques — Constraint, feasibility, and optimization cuts
2. Generate Permutations — Core combinatorial backtracking
3. N-Queens — Classic board constraint problem
4. Dynamic Programming Intro — When overlapping subproblems replace tree search

Practice Problems

Beginner Level:

• Letter Combinations of a Phone Number
• Subsets
• Combination Sum

Intermediate Level:

• Permutations
• Combinations
• N-Queens
• Word Search
• Sudoku Solver

Summary