Recursion & Backtracking — When to Apply

Part 1: Recursion

What is Recursion?

Recursion is a problem-solving technique where a function calls itself to solve smaller instances of the same problem. It is the computational analog of mathematical induction: prove the base case, assume the result for smaller inputs, and use that to solve the current case.

Every recursive solution has three components:

"Trust the recursion" is the single most important mental model. When writing a recursive function, assume that calls on smaller inputs return the correct answer. Your job is only to:

Handle the base case
Make the problem smaller
Combine the results correctly

The Call Stack

When a function calls itself, each call creates a stack frame with its own local variables. The frames stack up until a base case is reached, then unwind as each call returns.

CPP

int factorial(int n) {
    if (n <= 1) return 1;         // base case
    return n * factorial(n - 1);  // recursive case
}

Stack overflow occurs when recursion goes too deep (typically > 10,000 - 100,000 frames depending on the system). Always ensure:

Base case is reachable
Each recursive call makes progress toward the base case
For deep recursions (n > 10^4), consider converting to iteration

Recursion Patterns

Pattern 1: Linear Recursion

Each call makes one recursive call. The problem shrinks by a constant amount.

sum([5, 3, 8, 1], i=3)
  = 1 + sum([5, 3, 8, 1], i=2)
       = 8 + sum([5, 3, 8, 1], i=1)
            = 3 + sum([5, 3, 8, 1], i=0)
                 = 5 + sum([5, 3, 8, 1], i=-1)
                      = 0   ← base case
                 = 5 + 0 = 5
            = 3 + 5 = 8
       = 8 + 8 = 16
  = 1 + 16 = 17

CPP

int sum(vector<int>& arr, int i) {
    if (i < 0) return 0;              // base case
    return arr[i] + sum(arr, i - 1);  // one recursive call
}

Time: O(n) | Space: O(n) for call stack

Other examples: linear search, string reversal, computing power (naive).

Pattern 2: Binary Recursion (Tree Recursion)

Each call makes two recursive calls. Creates a binary tree of calls.

CPP

// SLOW: O(2^n) without memoization
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);  // TWO recursive calls
}

Why exponential? At each level, calls roughly double. Depth is n. Calls at level k ~= 2^k. Total ~= 2^0 + 2^1 + ... + 2^n = O(2^n).

Other examples: merge sort (but O(n log n) because work at each level is O(n)), tree traversals, Tower of Hanoi.

Pattern 3: Multiple Recursion (Subset/Choice Recursion)

At each step, make multiple choices, recursing for each. This is the foundation of backtracking.

CPP

void subsets(vector<int>& nums, int i, vector<int>& curr,
             vector<vector<int>>& result) {
    if (i == (int)nums.size()) {
        result.push_back(curr);  // reached a leaf: record this subset
        return;
    }
    // Choice 1: exclude nums[i]
    subsets(nums, i + 1, curr, result);
    // Choice 2: include nums[i]
    curr.push_back(nums[i]);
    subsets(nums, i + 1, curr, result);
    curr.pop_back();  // undo the choice (backtrack!)
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> curr;
    subsets(nums, 0, curr, result);
    return result;
}

Time: O(2^n * n) (2^n subsets, each up to size n to copy) | Space: O(n) stack depth

Pattern 4: Divide and Conquer

Split the problem into independent subproblems of roughly equal size, solve each, and combine the results. Unlike DP, subproblems do NOT overlap.

mergeSort([38, 27, 43, 3, 9, 82, 10])

Split:    [38, 27, 43, 3]    |    [9, 82, 10]
Split:  [38, 27] | [43, 3]   |  [9, 82] | [10]
Split: [38]|[27] [43]|[3]    | [9]|[82]  [10]
Merge: [27,38]  [3,43]       | [9,82]    [10]
Merge:  [3,27,38,43]         |  [9,10,82]
Merge:      [3, 9, 10, 27, 38, 43, 82]

CPP

void mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) return;               // base: single element
    int mid = l + (r - l) / 2;
    mergeSort(arr, l, mid);           // solve left half
    mergeSort(arr, mid + 1, r);       // solve right half
    merge(arr, l, mid, r);           // combine results
}

void merge(vector<int>& arr, int l, int mid, int r) {
    vector<int> tmp(r - l + 1);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
        else                  tmp[k++] = arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= r)   tmp[k++] = arr[j++];
    for (int p = 0; p < k; p++) arr[l + p] = tmp[p];
}

Time: O(n log n) (T(n) = 2T(n/2) + O(n) by Master theorem) | Space: O(n)

Other examples: quick sort, binary search, closest pair of points, Strassen's matrix multiplication.

Recursion to Iteration

Any recursion can be converted to iteration using an explicit stack. This avoids stack overflow for deep recursions.

General pattern:

CPP

// Recursive version
void dfs(Node* node) {
    if (!node) return;
    process(node);
    dfs(node->left);
    dfs(node->right);
}

// Iterative version using explicit stack
void dfs_iterative(Node* root) {
    if (!root) return;
    stack<Node*> stk;
    stk.push(root);
    while (!stk.empty()) {
        Node* node = stk.top();
        stk.pop();
        process(node);
        if (node->right) stk.push(node->right);  // right first (LIFO)
        if (node->left)  stk.push(node->left);   // so left is processed first
    }
}

When to convert:

Deep recursion (n > 10^4) risks stack overflow
You need explicit control over the traversal order
Performance-critical code where function call overhead matters

Tail Recursion

A function is tail-recursive when the recursive call is the very last operation — no computation happens after the call returns. Compilers can optimize tail recursion into a loop (tail call optimization / TCO), using O(1) stack space.

CPP

// NOT tail recursive: multiplication happens AFTER the recursive call
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // must wait for factorial(n-1) to multiply
}

// Tail recursive: accumulator carries the partial result
int factorial(int n, int acc = 1) {
    if (n <= 1) return acc;
    return factorial(n - 1, n * acc);  // nothing to do after this call returns
}

How the compiler optimizes tail recursion:

factorial(4, 1)
  → factorial(3, 4)       // just update n and acc, reuse stack frame
    → factorial(2, 12)
      → factorial(1, 24)
        → return 24

Equivalent to:
  while (n > 1) { acc *= n; n--; }
  return acc;

Note: C++ does NOT guarantee TCO (it's compiler-dependent, and -O2 or higher is usually needed). For production code, manually convert to iteration if stack depth is a concern.

Recursion Complexity Analysis

Pattern	Recurrence	Time	Space (stack)
Linear	T(n) = T(n-1) + O(1)	O(n)	O(n)
Binary/Tree	T(n) = 2T(n-1) + O(1)	O(2^n)	O(n)
Divide & Conquer	T(n) = 2T(n/2) + O(n)	O(n log n)	O(log n)
Subsets	T(n) = 2T(n-1) + O(n)	O(n * 2^n)	O(n)
Permutations	T(n) = n * T(n-1) + O(n)	O(n * n!)	O(n)

Use the Master theorem for divide-and-conquer recurrences: T(n) = aT(n/b) + O(n^d)

If d < log_b(a): O(n^(log_b(a)))
If d = log_b(a): O(n^d * log n)
If d > log_b(a): O(n^d)

Part 2: Backtracking

What is Backtracking?

Backtracking is a systematic method for exploring all possible solutions by building a solution incrementally, one choice at a time. When a partial solution can't possibly lead to a valid/optimal complete solution, we abandon it (backtrack) and try the next option.

Think of it as a depth-first search through the solution space, with pruning to cut off dead-end branches early.

The Backtracking Template

Nearly every backtracking problem follows this template:

CPP

void backtrack(State& state, Choices& choices, Results& results) {
    // 1. CHECK: Have we found a complete solution?
    if (isGoalState(state)) {
        results.add(state);
        return;
    }

    // 2. ITERATE: Try each available choice
    for (auto& choice : getAvailableChoices(choices)) {

        // 3. PRUNE: Skip invalid choices early
        if (!isValid(choice, state)) continue;

        // 4. CHOOSE: Make the choice (modify state)
        makeChoice(state, choice);

        // 5. EXPLORE: Recurse with the updated state
        backtrack(state, choices, results);

        // 6. UNCHOOSE: Undo the choice (restore state)
        undoChoice(state, choice);
    }
}

The three critical steps in the loop body form the DO-RECURSE-UNDO pattern:

Visual: The Decision Tree

Every backtracking problem can be visualized as a decision tree where:

Each level = one decision point
Each branch = one choice
Each leaf = a complete (or abandoned) solution
Pruning = cutting off entire subtrees

When to Apply Backtracking

Use backtracking when you need to:

Generate ALL valid configurations
- All subsets, permutations, combinations
- All valid parentheses strings
- All paths in a graph/grid satisfying constraints
Solve constraint satisfaction problems
- N-Queens: place queens without attacks
- Sudoku: fill grid following rules
- Graph coloring: color nodes with k colors
Search with constraints
- Word search in a grid
- Partition into valid groups
- Assign values satisfying conditions

The Key Questions Before Coding

Classic Backtracking Problems with Full Solutions

1. Subsets (LC 78)

Problem: Given a set of distinct integers, return all possible subsets.

Choices: For each element, include it or not. Alternatively, at each step, choose which remaining element to add next.

Decision tree (iterative inclusion approach):

{} ← start: empty set is a subset {1} {2} {3} ← add one element {1,2} {1,3} {2,3} ← add one more (larger indices only) {1,2,3} ← add one more All nodes are valid subsets: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}

Why start parameter? To avoid duplicates. If we've decided to include element at index 2, we only consider indices 3, 4, ... going forward. This ensures each subset is generated exactly once in a canonical order.

CPP

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> curr;
        backtrack(nums, 0, curr, result);
        return result;
    }

private:
    void backtrack(vector<int>& nums, int start,
                   vector<int>& curr, vector<vector<int>>& result) {
        result.push_back(curr);  // every partial solution is a valid subset

        for (int i = start; i < (int)nums.size(); i++) {
            curr.push_back(nums[i]);       // CHOOSE
            backtrack(nums, i + 1, curr, result);  // EXPLORE
            curr.pop_back();               // UNCHOOSE
        }
    }
};

Trace for [1, 2, 3]:

backtrack(start=0, curr=[])     → add [] to result
  i=0: curr=[1]                 → add [1]
    i=1: curr=[1,2]             → add [1,2]
      i=2: curr=[1,2,3]        → add [1,2,3]
      pop 3 → [1,2]
    pop 2 → [1]
    i=2: curr=[1,3]            → add [1,3]
    pop 3 → [1]
  pop 1 → []
  i=1: curr=[2]                → add [2]
    i=2: curr=[2,3]            → add [2,3]
    pop 3 → [2]
  pop 2 → []
  i=2: curr=[3]                → add [3]
  pop 3 → []

Result: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Time: O(2^n * n) | Space: O(n) recursion depth

Variant — Subsets II (LC 90): Input may have duplicates. Sort first, then skip duplicate choices at the same decision level:

CPP

void backtrack(vector<int>& nums, int start,
               vector<int>& curr, vector<vector<int>>& result) {
    result.push_back(curr);
    for (int i = start; i < (int)nums.size(); i++) {
        if (i > start && nums[i] == nums[i-1]) continue;  // skip duplicates!
        curr.push_back(nums[i]);
        backtrack(nums, i + 1, curr, result);
        curr.pop_back();
    }
}

2. Permutations (LC 46)

Problem: Given a collection of distinct integers, return all possible permutations.

Key difference from subsets: Order matters, and we use ALL elements. At each step, we choose from elements not yet used.

Decision tree:

[] [1] [2] [3] ← 3 choices [1,2] [1,3] [2,1] [2,3] [3,1] [3,2] ← 2 [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] ← 1

Approach 1: Used-array approach (straightforward):

CPP

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> curr;
        vector<bool> used(nums.size(), false);
        backtrack(nums, used, curr, result);
        return result;
    }

private:
    void backtrack(vector<int>& nums, vector<bool>& used,
                   vector<int>& curr, vector<vector<int>>& result) {
        if (curr.size() == nums.size()) {
            result.push_back(curr);
            return;
        }

        for (int i = 0; i < (int)nums.size(); i++) {
            if (used[i]) continue;        // skip already-used elements
            used[i] = true;               // CHOOSE
            curr.push_back(nums[i]);
            backtrack(nums, used, curr, result);  // EXPLORE
            curr.pop_back();              // UNCHOOSE
            used[i] = false;
        }
    }
};

Approach 2: Swap-based approach (more elegant, no extra space):

The idea: at position idx, swap each remaining element into that position, recurse, then swap back.

[1, 2, 3], idx=0
  swap(0,0) → [1, 2, 3], idx=1
    swap(1,1) → [1, 2, 3], idx=2 → swap(2,2) → record [1,2,3]
    swap(1,2) → [1, 3, 2], idx=2 → swap(2,2) → record [1,3,2]
    swap back → [1, 2, 3]
  swap(0,1) → [2, 1, 3], idx=1
    swap(1,1) → [2, 1, 3] → record [2,1,3]
    swap(1,2) → [2, 3, 1] → record [2,3,1]
    swap back → [2, 1, 3]
  swap back → [1, 2, 3]
  swap(0,2) → [3, 2, 1], idx=1
    swap(1,1) → [3, 2, 1] → record [3,2,1]
    swap(1,2) → [3, 1, 2] → record [3,1,2]
    swap back → [3, 2, 1]
  swap back → [1, 2, 3]

CPP

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        backtrack(nums, 0, result);
        return result;
    }

private:
    void backtrack(vector<int>& nums, int idx, vector<vector<int>>& result) {
        if (idx == (int)nums.size()) {
            result.push_back(nums);
            return;
        }
        for (int i = idx; i < (int)nums.size(); i++) {
            swap(nums[idx], nums[i]);           // CHOOSE
            backtrack(nums, idx + 1, result);   // EXPLORE
            swap(nums[idx], nums[i]);           // UNCHOOSE
        }
    }
};

Time: O(n! * n) | Space: O(n) recursion depth

3. Combination Sum (LC 39)

Problem: Given an array of distinct integers candidates and a target, find all unique combinations where candidates sum to target. Each number can be used unlimited times.

Key decisions:

Allow reuse: pass i (not i+1) when recursing
To avoid duplicates like [2,3,2] and [3,2,2]: only consider candidates from index start onward

Decision tree for candidates = [2, 3, 6, 7], target = 7:

target=7 use 2 use 3 use 6 use 7 rem=5 rem=4 rem=1 X rem=0 → [7] 2 3 6 7 r=3 r=2 X X 3 6 7 r=1 X X X 2 3 6 r=1 X r=0 → [2,2,3] X 3 r=-1 X Results: [2,2,3] and [7]

CPP

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> curr;
        backtrack(candidates, target, 0, curr, result);
        return result;
    }

private:
    void backtrack(vector<int>& cands, int remaining, int start,
                   vector<int>& curr, vector<vector<int>>& result) {
        if (remaining == 0) {
            result.push_back(curr);
            return;
        }
        if (remaining < 0) return;  // pruning

        for (int i = start; i < (int)cands.size(); i++) {
            if (cands[i] > remaining) continue;  // pruning (sort first for better pruning)
            curr.push_back(cands[i]);             // CHOOSE
            backtrack(cands, remaining - cands[i], i, curr, result);  // i, not i+1!
            curr.pop_back();                      // UNCHOOSE
        }
    }
};

Optimization: Sort candidates first. Then if cands[i] > remaining, we can break instead of continue (all subsequent candidates are even larger):

CPP

sort(candidates.begin(), candidates.end());
// In the loop:
if (cands[i] > remaining) break;  // early termination

Time: O(n^(target/min)) in the worst case | Space: O(target/min) recursion depth

Variant — Combination Sum II (LC 40): Each number used at most once, input may have duplicates. Use i+1 in recursion and skip duplicates:

CPP

sort(candidates.begin(), candidates.end());
// In the loop:
if (i > start && cands[i] == cands[i-1]) continue;  // skip same-level duplicates
backtrack(cands, remaining - cands[i], i + 1, curr, result);  // i+1: no reuse

4. N-Queens (LC 51)

Problem: Place n queens on an n x n chessboard so no two queens attack each other. A queen attacks along its row, column, and both diagonals.

Approach: Place one queen per row (guaranteed since queens can't share rows). For each row, try each column, checking if it's safe.

Visual: Constraint representation

A queen at (row, col) attacks:
- Column: col
- Diagonal ↘: row - col (constant along this diagonal)
- Diagonal ↗: row + col (constant along this diagonal)

  For a 4×4 board, the diagonal identifiers:

  row-col (↘ diagonals):       row+col (↗ diagonals):
    0  -1  -2  -3                0   1   2   3
    1   0  -1  -2                1   2   3   4
    2   1   0  -1                2   3   4   5
    3   2   1   0                3   4   5   6

Step-by-step for n=4:

Row 0: Try col 0
  . Q . .    Row 0: Try col 1
  . . . .      Row 1: col 0? diag conflict (1-0=1, 0-1=-1, but wait)
  . . . .               Let me redo with col tracking.
  . . . .

  cols = {1}, diag1 = {-1}, diag2 = {1}

  Row 1: col 0? diag2: 1+0=1 ∈ diag2? No (diag2={1}). Yes! 1 ∈ {1}. Conflict!
         col 1? col conflict (1 ∈ cols)
         col 2? diag1: 1-2=-1 ∈ diag1={-1}? Yes! Conflict!
         col 3? col 3 ok, diag1: 1-3=-2 not in {-1}, diag2: 1+3=4 not in {1}. Safe!

  . Q . .    cols={1,3}, diag1={-1,-2}, diag2={1,4}
  . . . Q
  . . . .    Row 2: col 0? diag1: 2-0=2, diag2: 2+0=2. Both clear. Safe!
  . . . .

  . Q . .    cols={0,1,3}, diag1={-1,-2,2}, diag2={1,2,4}
  . . . Q
  Q . . .    Row 3: col 0? col conflict. col 1? col conflict.
  . . . .            col 2? diag1: 3-2=1, diag2: 3+2=5. Both clear. Safe!

  . Q . .
  . . . Q    → SOLUTION FOUND!
  Q . . .    Positions: (0,1), (1,3), (2,0), (3,2)
  . . Q .

CPP

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> results;
        vector<string> board(n, string(n, '.'));
        unordered_set<int> cols, diag1, diag2;  // occupied columns and diagonals
        backtrack(n, 0, board, cols, diag1, diag2, results);
        return results;
    }

private:
    void backtrack(int n, int row, vector<string>& board,
                   unordered_set<int>& cols,
                   unordered_set<int>& diag1,  // row - col
                   unordered_set<int>& diag2,  // row + col
                   vector<vector<string>>& results) {
        if (row == n) {
            results.push_back(board);
            return;
        }

        for (int col = 0; col < n; col++) {
            // PRUNE: check all three constraints
            if (cols.count(col) || diag1.count(row - col) || diag2.count(row + col))
                continue;

            // CHOOSE
            board[row][col] = 'Q';
            cols.insert(col);
            diag1.insert(row - col);
            diag2.insert(row + col);

            // EXPLORE
            backtrack(n, row + 1, board, cols, diag1, diag2, results);

            // UNCHOOSE
            board[row][col] = '.';
            cols.erase(col);
            diag1.erase(row - col);
            diag2.erase(row + col);
        }
    }
};

Time: O(n!) — at row 0, n choices; at row 1, at most n-1; etc. Pruning makes it much faster in practice. | Space: O(n^2) for the board

5. Sudoku Solver (LC 37)

Problem: Fill a 9x9 Sudoku board so each row, column, and 3x3 box contains digits 1-9.

Approach: Find the next empty cell, try digits 1-9, check validity, recurse. If no digit works, backtrack.

Pruning strategy: Pre-compute which digits are available for each row, column, and box using sets or bitmasks.

CPP

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        // Pre-populate constraint sets
        vector<unordered_set<int>> rows(9), cols(9), boxes(9);
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] != '.') {
                    int d = board[r][c] - '0';
                    rows[r].insert(d);
                    cols[c].insert(d);
                    boxes[(r/3)*3 + c/3].insert(d);
                }
            }
        }
        backtrack(board, rows, cols, boxes, 0, 0);
    }

private:
    bool backtrack(vector<vector<char>>& board,
                   vector<unordered_set<int>>& rows,
                   vector<unordered_set<int>>& cols,
                   vector<unordered_set<int>>& boxes,
                   int r, int c) {
        // Move to next empty cell
        while (r < 9 && board[r][c] != '.') {
            c++;
            if (c == 9) { c = 0; r++; }
        }
        if (r == 9) return true;  // all cells filled!

        int box = (r/3)*3 + c/3;
        for (int d = 1; d <= 9; d++) {
            if (rows[r].count(d) || cols[c].count(d) || boxes[box].count(d))
                continue;  // PRUNE

            // CHOOSE
            board[r][c] = '0' + d;
            rows[r].insert(d);
            cols[c].insert(d);
            boxes[box].insert(d);

            // EXPLORE
            if (backtrack(board, rows, cols, boxes, r, c))
                return true;  // found solution, propagate success

            // UNCHOOSE
            board[r][c] = '.';
            rows[r].erase(d);
            cols[c].erase(d);
            boxes[box].erase(d);
        }
        return false;  // no digit works, backtrack
    }
};

Time: O(9^(empty cells)) worst case, but pruning makes it practical | Space: O(81)

Note: The function returns bool because we stop at the FIRST valid solution. This is a common pattern for "find one solution" vs "find all solutions".

6. Word Search (LC 79)

Problem: Given an m x n grid of characters and a string word, determine if the word exists in the grid by moving to adjacent cells (up, down, left, right). Each cell can be used at most once.

Approach: Try starting from each cell. From each cell, explore all 4 directions using backtracking. Mark cells as visited to prevent reuse.

Board:          Word: "ABCCED"
  A B C E
  S F C S       Path found:
  A D E E        A→B→C→C→E→D
                  (0,0)(0,1)(0,2)(1,2)(2,2) wait...
                  Let me trace:
                  A(0,0) → B(0,1) → C(0,2) → C(1,2) → E(2,2)?
                  No, E is at (0,3) and (2,2) and (2,3).

                  A(0,0) → B(0,1) → C(0,2) → C(1,2) → E(2,2) → D(2,1) ✓

                  [A] [B] [C]  E
                   S   F  [C]  S
                   A  [D] [E]  E

CPP

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (backtrack(board, word, i, j, 0))
                    return true;
            }
        }
        return false;
    }

private:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    bool backtrack(vector<vector<char>>& board, string& word,
                   int r, int c, int idx) {
        if (idx == (int)word.size()) return true;  // matched all characters

        int m = board.size(), n = board[0].size();
        if (r < 0 || r >= m || c < 0 || c >= n) return false;  // out of bounds
        if (board[r][c] != word[idx]) return false;             // character mismatch

        // CHOOSE: mark as visited
        char saved = board[r][c];
        board[r][c] = '#';

        // EXPLORE: try all 4 directions
        for (int d = 0; d < 4; d++) {
            if (backtrack(board, word, r + dx[d], c + dy[d], idx + 1))
                return true;
        }

        // UNCHOOSE: restore
        board[r][c] = saved;
        return false;
    }
};

Time: O(m * n * 3^L) where L = word length. At each step, 3 choices (can't go back to where we came from). | Space: O(L) recursion depth

7. Palindrome Partitioning (LC 131)

Problem: Partition a string such that every substring is a palindrome. Return all such partitions.

Choices: At each position, try every possible palindrome starting there.

Decision tree for "aab":

"aab" "a" | "ab" "aa" | "b" "aab" (not palindrome) "a" | "b" X (not pal) "b" "a","a","b" "aa","b"

CPP

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> curr;
        backtrack(s, 0, curr, result);
        return result;
    }

private:
    bool isPalindrome(string& s, int l, int r) {
        while (l < r) {
            if (s[l] != s[r]) return false;
            l++; r--;
        }
        return true;
    }

    void backtrack(string& s, int start,
                   vector<string>& curr, vector<vector<string>>& result) {
        if (start == (int)s.size()) {
            result.push_back(curr);
            return;
        }

        for (int end = start; end < (int)s.size(); end++) {
            if (!isPalindrome(s, start, end)) continue;  // PRUNE

            curr.push_back(s.substr(start, end - start + 1));  // CHOOSE
            backtrack(s, end + 1, curr, result);                // EXPLORE
            curr.pop_back();                                    // UNCHOOSE
        }
    }
};

Optimization: Precompute a palindrome table using DP (like in Palindrome Partitioning II) to check isPalindrome(i, j) in O(1) instead of O(n).

Time: O(n * 2^n) worst case | Space: O(n)

8. Letter Combinations of a Phone Number (LC 17)

Problem: Given a string of digits 2-9, return all possible letter combinations.

CPP

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};

        vector<string> mapping = {
            "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        };

        vector<string> result;
        string curr;
        backtrack(digits, mapping, 0, curr, result);
        return result;
    }

private:
    void backtrack(string& digits, vector<string>& mapping, int idx,
                   string& curr, vector<string>& result) {
        if (idx == (int)digits.size()) {
            result.push_back(curr);
            return;
        }

        string& letters = mapping[digits[idx] - '0'];
        for (char c : letters) {
            curr.push_back(c);              // CHOOSE
            backtrack(digits, mapping, idx + 1, curr, result);  // EXPLORE
            curr.pop_back();                // UNCHOOSE
        }
    }
};

Time: O(4^n * n) where n = number of digits (4 because '7' and '9' have 4 letters) | Space: O(n) recursion depth

9. Generate Parentheses (LC 22)

Problem: Generate all combinations of n pairs of well-formed parentheses.

Choices: At each position, place ( or ). Constraints:

Can place ( if open count < n
Can place ) if close count < open count

CPP

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string curr;
        backtrack(n, 0, 0, curr, result);
        return result;
    }

private:
    void backtrack(int n, int open, int close,
                   string& curr, vector<string>& result) {
        if ((int)curr.size() == 2 * n) {
            result.push_back(curr);
            return;
        }

        if (open < n) {
            curr.push_back('(');
            backtrack(n, open + 1, close, curr, result);
            curr.pop_back();
        }
        if (close < open) {
            curr.push_back(')');
            backtrack(n, open, close + 1, curr, result);
            curr.pop_back();
        }
    }
};

Time: O(4^n / sqrt(n)) — the nth Catalan number | Space: O(n)

Backtracking Optimizations

1. Pruning — The Most Important Optimization

Pruning eliminates entire subtrees that can't lead to valid solutions. Good pruning can reduce exponential search by orders of magnitude.

Types of pruning:

Constraint pruning: Check if placing this choice violates a constraint
Bound pruning: If the best possible result from here can't beat the current best, stop
Symmetry pruning: If the problem has symmetry, eliminate equivalent branches

2. Sorting the Input

Sorting often enables more effective pruning by trying "smaller" or "closer" choices first.

CPP

// Combination Sum: sort to enable early termination
sort(candidates.begin(), candidates.end());
for (int i = start; i < n; i++) {
    if (candidates[i] > remaining) break;  // all larger, stop!
    // ...
}

3. Skipping Duplicates

When the input has duplicate values, duplicates at the same decision level produce identical subtrees. Skip them.

CPP

sort(nums.begin(), nums.end());
for (int i = start; i < n; i++) {
    if (i > start && nums[i] == nums[i-1]) continue;  // skip duplicate
    // ...
}

4. Bitmask for Visited/Used State

For small sets (n <= 20), a bitmask integer is faster than a boolean array for tracking which elements are used.

CPP

// Instead of vector<bool> used(n, false):
int used = 0;

// Check if i-th element is used:
if (used & (1 << i)) ...

// Mark i-th element as used:
used |= (1 << i);

// Unmark:
used &= ~(1 << i);

// Advantage: copying an int is O(1), copying a vector is O(n)
// Also useful for hashing states in memoization

5. Constraint Propagation

For problems like Sudoku, after placing a digit, propagate its effects to reduce future choices. If any cell has zero valid choices, immediately backtrack.

Place 5 at (0,0):
  → Remove 5 from all cells in row 0, column 0, and box 0
  → Cell (0,3) now has only one valid digit → place it automatically
  → This cascading propagation dramatically prunes the search space

Recursion vs Backtracking vs Dynamic Programming

When to Use Each

Decision Flowchart

The Key Differences

Aspect	Backtracking	Dynamic Programming
Goal	Find ALL solutions	Find the BEST solution or COUNT
Approach	Try all, prune invalid	Break into overlapping subproblems
State	Built incrementally (mutable)	Stored in table (immutable)
Optimization	Pruning	Memoization / Tabulation
Output	List of solutions	Single value (or one optimal solution)
Example	"Print all permutations"	"Count permutations" or "best permutation"

When Backtracking Becomes DP

If you notice your backtracking solution revisits the same state multiple times, you can memoize it — turning backtracking into top-down DP.

Example: Word Break

Backtracking: try every split, recurse on the remainder
  → same suffix "code" might be checked from multiple split points
  → add memoization: memo[i] = can s[i..n-1] be broken?
  → now it's DP!

Complexity of Backtracking Solutions

Time Complexity Cheat Sheet

Space Complexity

For all backtracking solutions, the recursion depth determines stack space:

Subsets/Permutations: O(n)
Word Search: O(word length)
Sudoku: O(81) = O(1)
N-Queens: O(n)

Plus any auxiliary data structures (visited sets, constraint tracking).

Additional Classic Problems — Quick Solutions

Combinations (LC 77)

Generate all combinations of k numbers from [1, n].

CPP

void backtrack(int n, int k, int start, vector<int>& curr,
               vector<vector<int>>& result) {
    if ((int)curr.size() == k) {
        result.push_back(curr);
        return;
    }
    // Pruning: need k - curr.size() more elements, so stop if not enough remain
    for (int i = start; i <= n - (k - (int)curr.size()) + 1; i++) {
        curr.push_back(i);
        backtrack(n, k, i + 1, curr, result);
        curr.pop_back();
    }
}

Restore IP Addresses (LC 93)

Partition a digit string into 4 valid IP octets (0-255).

CPP

void backtrack(string& s, int start, int parts, string& curr,
               vector<string>& result) {
    if (parts == 4 && start == (int)s.size()) {
        result.push_back(curr.substr(0, curr.size() - 1));  // remove trailing dot
        return;
    }
    if (parts == 4 || start == (int)s.size()) return;

    for (int len = 1; len <= 3 && start + len <= (int)s.size(); len++) {
        string part = s.substr(start, len);
        if ((part.size() > 1 && part[0] == '0') || stoi(part) > 255) continue;
        string next = curr + part + ".";
        backtrack(s, start + len, parts + 1, next, result);
    }
}

Summary: The Backtracking Mindset

Practice strategy: Start with Subsets (simplest), then Permutations (add "used" tracking), then Combination Sum (add sum constraint), then N-Queens (add complex constraints with efficient pruning). Once comfortable, tackle Sudoku and Word Search. For each problem, always draw the decision tree first — the code writes itself once you see the tree.