Common Backtracking Patterns

TL;DR

• Bottom line: Backtracking systematically explores all candidate solutions via recursive choose-explore-unchoose, pruning invalid branches early to avoid full exponential search.
• Key tool: The recursive backtrack(path, choices) template with state restoration after each recursive call.
• Watch out for: Forgetting to undo state changes after recursion (the "unchoose" step), which silently corrupts remaining branches.
• Works with: Any language with recursion; patterns are language-agnostic. Most commonly implemented in Python, Java, JavaScript, and C++.

Constraints

• Backtracking has worst-case exponential time O(b^d) where b is branching factor and d is depth; always estimate feasibility before implementing
• State must be fully restored after each recursive call (choose-explore-unchoose); partial undo causes silent corruption of later branches
• Pruning is not optional for production use; unpruned backtracking is computationally infeasible for non-trivial inputs
• Base case must terminate recursion; missing or incorrect base case causes infinite recursion / stack overflow
• Mutable shared state (arrays, sets) must be passed by reference and restored, not copied per call, to avoid O(n!) space blowup

Quick Reference

Decision Tree

START: Do you need to enumerate ALL valid solutions (not just count or optimize)?
├── YES: Is there a constraint that eliminates large branches early?
│   ├── YES → Backtracking with pruning (this unit)
│   └── NO → Backtracking still works but may be slow; check if problem size allows exponential time
├── NO: Do subproblems overlap (same state reachable via different paths)?
│   ├── YES → Dynamic Programming
│   └── NO ↓
├── Need shortest path / minimum steps in state space?
│   ├── YES → BFS (breadth-first search)
│   └── NO ↓
├── Can you prove greedy choice property?
│   ├── YES → Greedy algorithm
│   └── NO ↓
└── DEFAULT → Backtracking with pruning is the safe fallback for constraint satisfaction

Step-by-Step Guide

1. Identify the backtracking structure

Determine what constitutes a "choice" at each step, what the "path" (partial solution) looks like, and when you've reached a complete solution (base case). Draw the decision tree on paper first. [src1]

Three key concepts:
- PATH:    choices already made (the partial solution so far)
- CHOICES: options available at the current step
- BASE:    condition where path is a complete valid solution

Verify: Can you draw a tree where each level represents one choice? If yes, backtracking applies.

2. Write the general template

Every backtracking solution follows this skeleton. Customize the three marked sections. [src1]

def backtrack(path, choices):
    if is_complete(path):          # BASE CASE
        result.append(path[:])     # save a copy
        return
    for choice in choices:
        if not is_valid(choice):   # PRUNE
            continue
        path.append(choice)        # CHOOSE
        backtrack(path, next_choices)  # EXPLORE
        path.pop()                 # UNCHOOSE (undo)

Verify: Every append has a matching pop, and the base case copies the path.

3. Add pruning to reduce search space

Without pruning, you explore every branch. Add constraints that skip invalid choices before recursing. [src3]

# Combination sum: prune when remaining target < 0
def backtrack(path, start, remaining):
    if remaining == 0:
        result.append(path[:])
        return
    for i in range(start, len(candidates)):
        if candidates[i] > remaining:  # PRUNE
            break
        path.append(candidates[i])
        backtrack(path, i, remaining - candidates[i])
        path.pop()

Verify: Sort input first when using comparison-based pruning.

4. Handle duplicates

Sort the input, then skip consecutive duplicates at the same decision level. [src2]

candidates.sort()
for i in range(start, len(candidates)):
    if i > start and candidates[i] == candidates[i - 1]:
        continue  # skip duplicate at same level
    # ... choose, explore, unchoose

Verify: Output should contain no duplicate subsets/combinations. Test with [1, 1, 2].

Code Examples

Python: Subsets (Power Set)

# Input:  nums = [1, 2, 3]
# Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(path[:])      # collect at every node
        for i in range(start, len(nums)):
            path.append(nums[i])    # choose
            backtrack(i + 1, path)  # explore (i+1 prevents reuse)
            path.pop()              # unchoose
    backtrack(0, [])
    return result

Python: N-Queens

# Input:  n = 4
# Output: all valid board configurations as lists of queen positions

def solve_n_queens(n):
    result, cols, diags, anti = [], set(), set(), set()
    def backtrack(row, queens):
        if row == n:
            result.append(queens[:])
            return
        for col in range(n):
            if col in cols or (row-col) in diags or (row+col) in anti:
                continue              # prune: conflict detected
            cols.add(col); diags.add(row-col); anti.add(row+col)
            backtrack(row + 1, queens + [col])
            cols.remove(col); diags.remove(row-col); anti.remove(row+col)
    backtrack(0, [])
    return result

JavaScript: Permutations

// Input:  nums = [1, 2, 3]
// Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

function permute(nums) {
  const result = [];
  function backtrack(path, used) {
    if (path.length === nums.length) { result.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;         // skip already-used elements
      used[i] = true; path.push(nums[i]);  // choose
      backtrack(path, used);                // explore
      path.pop(); used[i] = false;          // unchoose
    }
  }
  backtrack([], new Array(nums.length).fill(false));
  return result;
}

JavaScript: Combination Sum

// Input:  candidates = [2,3,6,7], target = 7
// Output: [[2,2,3],[7]]

function combinationSum(candidates, target) {
  candidates.sort((a, b) => a - b);
  const result = [];
  function backtrack(start, path, remaining) {
    if (remaining === 0) { result.push([...path]); return; }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break;  // prune
      path.push(candidates[i]);
      backtrack(i, path, remaining - candidates[i]); // i, not i+1 (reuse)
      path.pop();
    }
  }
  backtrack(0, [], target);
  return result;
}

Java: Sudoku Solver

Full script: SudokuSolver.java (45 lines)

// Input:  9x9 board with '.' for empty cells
// Output: solved board in-place

public void solveSudoku(char[][] board) { solve(board); }
private boolean solve(char[][] board) {
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++)
            if (board[r][c] == '.') {
                for (char d = '1'; d <= '9'; d++) {
                    if (isValid(board, r, c, d)) {
                        board[r][c] = d;       // choose
                        if (solve(board)) return true;  // explore
                        board[r][c] = '.';     // unchoose
                    }
                }
                return false;  // no valid digit: trigger backtrack
            }
    return true;  // all cells filled
}

Java: Palindrome Partitioning

// Input:  s = "aab"
// Output: [["a","a","b"],["aa","b"]]

public List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<>();
    backtrack(s, 0, new ArrayList<>(), result);
    return result;
}
void backtrack(String s, int start, List<String> path, List<List<String>> result) {
    if (start == s.length()) { result.add(new ArrayList<>(path)); return; }
    for (int end = start + 1; end <= s.length(); end++) {
        String sub = s.substring(start, end);
        if (!isPalindrome(sub)) continue;  // prune non-palindromes
        path.add(sub);
        backtrack(s, end, path, result);
        path.remove(path.size() - 1);
    }
}

Anti-Patterns

Wrong: Forgetting to undo state changes

# BAD -- missing path.pop() after recursion
def backtrack(path, start):
    result.append(path[:])
    for i in range(start, len(nums)):
        path.append(nums[i])
        backtrack(path, i + 1)
        # forgot path.pop() -- path grows forever, all results wrong

Correct: Always undo after recursion

# GOOD -- symmetric choose/unchoose
def backtrack(path, start):
    result.append(path[:])
    for i in range(start, len(nums)):
        path.append(nums[i])     # choose
        backtrack(path, i + 1)   # explore
        path.pop()               # unchoose -- MUST match the append

Wrong: Storing reference instead of copy

# BAD -- appending the same list object, not a snapshot
def backtrack(path, start):
    if len(path) == k:
        result.append(path)       # all entries point to same list!

Correct: Copy the path before storing

# GOOD -- append a shallow copy
def backtrack(path, start):
    if len(path) == k:
        result.append(path[:])    # path[:] or list(path) creates a copy

Wrong: No pruning on sorted candidates

# BAD -- tries every candidate even when sum exceeds target
for i in range(start, len(candidates)):
    path.append(candidates[i])
    backtrack(path, i, remaining - candidates[i])
    path.pop()

Correct: Break early when candidate exceeds remaining

# GOOD -- sort first, break when too large
candidates.sort()
for i in range(start, len(candidates)):
    if candidates[i] > remaining:
        break                     # all subsequent also too large
    path.append(candidates[i])
    backtrack(path, i, remaining - candidates[i])
    path.pop()

Wrong: Not handling duplicates at same level

# BAD -- produces duplicate subsets for input [1, 1, 2]
for i in range(start, len(nums)):
    path.append(nums[i])
    backtrack(path, i + 1)
    path.pop()

Correct: Skip duplicates at same level after sorting

# GOOD -- skip nums[i] if equals nums[i-1] at same decision level
nums.sort()
for i in range(start, len(nums)):
    if i > start and nums[i] == nums[i - 1]:
        continue                  # skip duplicate at same tree level
    path.append(nums[i])
    backtrack(path, i + 1)
    path.pop()

Common Pitfalls

• Stack overflow on deep recursion: Python default limit is 1000. For deep backtracking, increase with sys.setrecursionlimit() or convert to iterative with explicit stack. [src3]
• O(n!) space from copying path at every node: Copy path only at leaf/base-case nodes, not at every recursive call. Move result.append(path[:]) inside the base case check. [src1]
• Using start parameter for permutations: Permutations need a used[] boolean array, not a start index. Using start produces combinations. Fix: use visited[i] to track used elements. [src2]
• Mutating the choices list during iteration: Removing/adding elements while iterating causes skipped or duplicated entries. Fix: use index-based iteration with start parameter. [src4]
• Incorrect diagonal check in N-Queens: Using O(n) scan per placement instead of O(1) set lookups. Fix: use three sets (cols, diags, anti_diags) for O(1) conflict detection. [src7]
• Not sorting before duplicate skipping: The nums[i] == nums[i-1] skip logic only works on sorted input. Fix: always sort() first. [src2]

When to Use / When Not to Use

Important Caveats

• Backtracking is fundamentally exponential; no amount of pruning changes the worst case. For n > 20-25 (subsets) or n > 10-12 (permutations), consider whether full enumeration is truly required.
• The choose-explore-unchoose pattern assumes mutable state. In functional languages or immutable-data contexts, pass new copies at each level instead -- this trades space for correctness simplicity.
• Many "backtracking" interview problems have DP solutions that are asymptotically faster for counting/optimizing. Always ask: "Do I need all solutions, or just the count/optimum?"
• For constraint satisfaction problems (CSP) at scale, dedicated CSP solvers (OR-Tools, Z3) vastly outperform hand-written backtracking.