patternDSA/Backtracking

Core Pattern → Pattern 25

Backtracking

Build a solution incrementally, abandoning a branch the moment it can't possibly lead to a valid answer. Choose. Explore. Unchoose. One template, every combinatorial search problem.

Frequency:★★★★★

·~35 min·Intermediate–Hard·5 problems

Prev Dynamic Programming

The Core Shock

Brute force generates every candidate then filters. Backtracking abandons a branch the instant it can't succeed — pruning the exponential tree dramatically.

Brute force

Generate all

Build every possible combination, check each against constraints. O(n!) or O(2^n) with full enumeration.

Backtracking

Prune early

Check constraints incrementally. Abandon dead branches before fully building them. Same worst case, but massively pruned in practice.

The key: backtracking explores a decision tree. At each node, you make a choice, recurse into the subtree, then undo the choice to try the next option. If a partial solution already violates a constraint, you prune the entire subtree — potentially saving millions of recursive calls.

The Universal Template

Memorise this. Every backtracking problem is a variation.

CHOOSE

Add the current candidate to the path. Update any state that tracks what's been used (visited set, running sum, etc.).

path.append(choice)
mark_used(choice)

EXPLORE

Recurse with the updated path. The recursive call explores all possibilities from the current state. Return when the base case is hit.

backtrack(
  path, remaining
)

UNCHOOSE

Undo the choice. Remove from path, unmark as used. The state must be identical to before the CHOOSE step.

path.pop()
unmark_used(choice)

path.copy() is mandatory when adding to results — path is mutated throughout
Prune before recursing: check constraints after CHOOSE, before EXPLORE
State symmetry: after backtrack() returns, state must equal state before backtrack() was called

The 3-Step Framework

Three decisions determine your backtracking solution.

Define what a complete solution looks like

This is your base case. For combination sum: path sums to target. For word search: index equals word length. For sudoku: no empty cells. When you hit the base case, record path.copy() and return.

# Combination Sum: remaining == 0
if remaining == 0:
    result.append(path.copy())
    return

# Word Search: matched all chars
if index == len(word):
    return True

If base case returns True/False (existence), return immediately on True. If collecting all solutions, always copy path before appending — appending path directly gives references to the same mutated list.

Define what makes a branch unpromising (pruning)

This is where backtracking beats brute force. Prune as early as possible: if current sum exceeds target, stop. If current cell is out of bounds or already visited, stop. If current digit fails sudoku constraints, skip. Every pruned node = entire subtree avoided.

# Combination Sum: sorted → break early
if candidate > remaining:
    break           # all further candidates also too big

# Word Search: multiple checks in one condition
if (r<0 or r>=rows or c<0 or c>=cols
    or board[r][c]=='#'
    or board[r][c]!=word[idx]):
    return False

Sort candidates when possible — it enables break instead of continue, pruning entire tails of the candidate list. For grid problems, combine all prune checks into one compound if to short-circuit early.

Define the search space (what choices to explore)

What are the candidates at each step? For combination sum: all candidates from start index onward (sorted, allows reuse). For word search: 4 adjacent cells. For sudoku: digits 1–9. For substrings: all possible ending positions. The search space defines your branching factor.

# Combinations with reuse
for i in range(start, len(candidates)):
    backtrack(i, ...)  # i not i+1

# Without reuse (permutations/subsets)
for i in range(start, len(nums)):
    backtrack(i+1, ...)  # i+1

Pass i (not i+1) to allow reuse of the same element. Pass i+1 to prevent reuse. Sort + skip duplicates (if nums[i]==nums[i-1] and i>start: continue) to avoid duplicate combinations from duplicate inputs.

Pattern Recognition

'Find ALL …' or 'does a solution EXIST' → backtracking.

Use Backtracking When

"Find ALL combinations that sum to target"

"Does word exist in grid?"

"Find all factor combinations of n"

"Solve Sudoku" / "Solve N-Queens"

"Generate all valid parentheses"

"Palindrome partitioning"

"Split string into max unique substrings"

Any "find/generate all valid ___" problem

Common Pitfalls

result.append(path) — appends reference, not copy! Use path.copy()

Combination sum reuse: passing i+1 instead of i — no reuse allowed

Combination sum no-reuse: passing i instead of i+1 — allows duplicates

Word search: forgetting to restore board[r][c] after recursion

Word search: not checking visited before recursing — revisits cells

Sudoku: not checking if found=True before continuing inner loops

Duplicate inputs: not sorting + skipping to avoid duplicate combinations

Pruning too late: checking after recursion instead of before

On this page