Recursion & Backtracking

The Mental Model

Recursion is delegation. Instead of solving the whole problem, you solve a smaller version and combine results. Backtracking is systematic trial and error—try a choice, explore all consequences, undo the choice, try the next. Analogy: Imagine you manage a team. Instead of doing all the work yourself, you hand a slightly smaller version of the task to a subordinate, who hands an even smaller version to their subordinate, until someone gets a trivially small task and just does it. The answers bubble back up the chain. That is recursion. Backtracking adds: “if the subordinate reports failure, try a different subordinate.”

Pattern Recognition Signals:

“Generate all combinations/permutations”
“Find all valid configurations”
Problem has natural substructure (solve for n-1, then n)
Constraints are small (n ≤ 20 for backtracking, n ≤ 10 for permutations)

When to Use

Recursion

Tree/graph traversals
Divide and conquer
Problems with substructure
DP (memoized recursion)

Backtracking

Generate combinations/subsets
Permutations
Constraint satisfaction (Sudoku, N-Queens)
Path finding with constraints

The Recursion Framework

Every recursive function has three parts:

ReturnType solve(State state) {
    // 1. BASE CASE: When to stop
    if (isBaseCase(state)) {
        return baseResult;
    }
    
    // 2. RECURSIVE CASE: Break into subproblems
    State newState = transformState(state);
    ReturnType subResult = solve(newState);
    
    // 3. COMBINE: Build answer from subproblem answers
    return combine(subResult);
}

Pattern 1: Subsets (Power Set)

Problem: Generate all 2^n subsets of an array. Approach: For each element, make two choices: include it or don’t. Analogy: Imagine standing at a buffet with n dishes. At each dish, you decide “take it” or “skip it.” Every possible combination of takes and skips is a subset. With n dishes, you make n binary decisions, giving 2^n total subsets. Worked example: nums = [1, 2, 3]

backtrack(0): Include 1
  backtrack(1): Include 2
    backtrack(2): Include 3 -> {1,2,3}
    backtrack(2): Exclude 3 -> {1,2}
  backtrack(1): Exclude 2
    backtrack(2): Include 3 -> {1,3}
    backtrack(2): Exclude 3 -> {1}
backtrack(0): Exclude 1
  (similar, giving {2,3}, {2}, {3}, {})

Result: 8 subsets = 2^3

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> current;
    
    function<void(int)> backtrack = [&](int index) {
        // Base case: processed all elements
        if (index == nums.size()) {
            result.push_back(current);
            return;
        }
        
        // Choice 1: Include nums[index]
        current.push_back(nums[index]);
        backtrack(index + 1);
        current.pop_back();  // Undo choice (backtrack)
        
        // Choice 2: Exclude nums[index]
        backtrack(index + 1);
    };
    
    backtrack(0);
    return result;
}

Time Complexity: O(2ⁿ) subsets, O(n) to copy each = O(n × 2ⁿ) Codeforces Problems:

Problem	Rating	Link
Good Sequences	1500	CF 264B

Pattern 2: Permutations

Problem: Generate all n! permutations. Approach: Fix each element at the current position, recurse for the rest.

vector<vector<int>> permutations(vector<int>& nums) {
    vector<vector<int>> result;
    
    function<void(int)> backtrack = [&](int start) {
        if (start == nums.size()) {
            result.push_back(nums);
            return;
        }
        
        for (int i = start; i < nums.size(); i++) {
            swap(nums[start], nums[i]);  // Fix nums[i] at position start
            backtrack(start + 1);
            swap(nums[start], nums[i]);  // Backtrack
        }
    };
    
    backtrack(0);
    return result;
}

Alternative: Using visited array

vector<vector<int>> permutations(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> current;
    vector<bool> used(nums.size(), false);
    
    function<void()> backtrack = [&]() {
        if (current.size() == nums.size()) {
            result.push_back(current);
            return;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            
            used[i] = true;
            current.push_back(nums[i]);
            backtrack();
            current.pop_back();
            used[i] = false;
        }
    };
    
    backtrack();
    return result;
}

Pattern 3: Combinations

Problem: Generate all C(n, k) combinations of size k. Key Insight: Like subsets, but only output when we have exactly k elements. The pruning line is critical: current.size() + (n - start + 1) < k checks whether there are enough remaining elements to fill the combination. Without this, you explore branches that can never lead to a valid combination — wasting exponential time. For example, if you need 5 elements but only 3 remain, there is no point continuing.

vector<vector<int>> combinations(int n, int k) {
    vector<vector<int>> result;
    vector<int> current;
    
    function<void(int)> backtrack = [&](int start) {
        // Found valid combination of exactly k elements
        if (current.size() == k) {
            result.push_back(current);
            return;
        }
        
        // Pruning: not enough elements remaining to complete a combination
        // We have current.size() elements, need k total, and can pick from start..n
        if (current.size() + (n - start + 1) < k) {
            return;
        }
        
        for (int i = start; i <= n; i++) {
            current.push_back(i);
            backtrack(i + 1);  // Start from i+1 to enforce increasing order (no duplicates)
            current.pop_back();
        }
    };
    
    backtrack(1);
    return result;
}
// Example: combinations(4, 2) = {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}

Pattern 4: Constraint Satisfaction

Problem: N-Queens - Place N queens on NxN board so none attack each other. Approach: Place queens row by row, check constraints before placing. Why row-by-row? Since no two queens can share a row, there is exactly one queen per row. This reduces the search space from C(n^2, n) positions to n^n positions (one column choice per row), and with constraint checking, most branches are pruned immediately. Diagonal indexing trick: For an NxN board, cells on the same ”/” diagonal have the same row + col value, and cells on the same "" diagonal have the same row - col value. We add n to row - col to keep indices non-negative.

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result;
    vector<string> board(n, string(n, '.'));
    
    // Track which columns and diagonals are under attack
    // cols[c] = true if column c has a queen
    // diag1[row-col+n] = true if "\" diagonal is occupied
    // diag2[row+col] = true if "/" diagonal is occupied
    vector<bool> cols(n), diag1(2 * n), diag2(2 * n);
    
    function<void(int)> backtrack = [&](int row) {
        if (row == n) {
            result.push_back(board);  // All n queens placed successfully
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (cols[col] || diag1[row - col + n] || diag2[row + col]) {
                continue;  // Position under attack -- constraint pruning
            }
            
            // Place queen and mark all three attack lines
            board[row][col] = 'Q';
            cols[col] = diag1[row - col + n] = diag2[row + col] = true;
            
            backtrack(row + 1);
            
            // Remove queen (backtrack) -- restore all three attack lines
            board[row][col] = '.';
            cols[col] = diag1[row - col + n] = diag2[row + col] = false;
        }
    };
    
    backtrack(0);
    return result;
}
// For n=4: 2 solutions. For n=8: 92 solutions.

Pattern 5: Path Finding with Backtracking

Problem: Find all paths from start to end in a graph/grid.

void findPaths(vector<vector<int>>& grid, int row, int col,
               vector<pair<int, int>>& path, vector<vector<pair<int, int>>>& result) {
    int n = grid.size(), m = grid[0].size();
    
    // Out of bounds or blocked
    if (row < 0 || row >= n || col < 0 || col >= m || grid[row][col] == 0) {
        return;
    }
    
    path.push_back({row, col});
    
    // Reached destination
    if (row == n - 1 && col == m - 1) {
        result.push_back(path);
    } else {
        // Mark as visited
        int temp = grid[row][col];
        grid[row][col] = 0;
        
        // Explore all directions
        findPaths(grid, row + 1, col, path, result);
        findPaths(grid, row, col + 1, path, result);
        findPaths(grid, row - 1, col, path, result);
        findPaths(grid, row, col - 1, path, result);
        
        // Backtrack
        grid[row][col] = temp;
    }
    
    path.pop_back();
}

The Backtracking Template

void backtrack(State state, Choices& choices, Results& results) {
    // Base case: found a valid solution
    if (isComplete(state)) {
        results.add(state);
        return;
    }
    
    for (Choice c : getChoices(state)) {
        // Pruning: skip invalid choices early
        if (!isValid(state, c)) continue;
        
        // Make choice
        applyChoice(state, c);
        
        // Recurse
        backtrack(state, choices, results);
        
        // Undo choice (backtrack)
        undoChoice(state, c);
    }
}

Pruning: The Key to Efficiency

Backtracking can be slow (exponential). Pruning cuts branches early. Analogy: Think of exploring a maze. Without pruning, you explore every dead end fully before backtracking. With pruning, you notice “this corridor is a dead end” before walking all the way in. The earlier you prune, the more time you save. In contest problems, good pruning can turn a TLE into an AC on the same algorithm.

Types of Pruning

Constraint Pruning: Skip choices that violate constraints (e.g., queen attacks another queen)
Bound Pruning: Skip if current path cannot lead to a better solution than the best so far
Symmetry Pruning: Skip symmetric configurations (e.g., in N-Queens, only check half the first-row positions)

// Example: Subset sum with pruning
void subsetSum(vector<int>& nums, int index, int currentSum, int target,
               vector<int>& current, vector<vector<int>>& result) {
    if (currentSum == target) {
        result.push_back(current);
        return;
    }
    
    for (int i = index; i < nums.size(); i++) {
        // Pruning: if adding nums[i] exceeds target, skip (assumes sorted)
        if (currentSum + nums[i] > target) break;
        
        // Skip duplicates
        if (i > index && nums[i] == nums[i - 1]) continue;
        
        current.push_back(nums[i]);
        subsetSum(nums, i + 1, currentSum + nums[i], target, current, result);
        current.pop_back();
    }
}

Common Mistakes

Mistake 1: Forgetting to Backtrack

// WRONG
current.push_back(nums[i]);
backtrack(i + 1);
// Missing: current.pop_back();

// CORRECT
current.push_back(nums[i]);
backtrack(i + 1);
current.pop_back();  // Restore state

Mistake 2: Stack Overflow Deep recursion (depth > 10⁴) can overflow the stack.

Use iterative approach
Increase stack size: ulimit -s unlimited (Linux)
For Codeforces, recursion depth > 10⁵ often fails

Mistake 3: Wrong Base Case The base case must handle the smallest valid input:

// WRONG: Infinite recursion
if (n < 0) return 0;  // What about n = 0?

// CORRECT
if (n == 0) return 1;  // Or appropriate base value
if (n < 0) return 0;

Recursion vs Iteration

Aspect	Recursion	Iteration
Readability	Often cleaner	Can be verbose
Space	O(depth) stack	O(1) usually
Speed	Function call overhead	Slightly faster
Stack overflow risk	Yes (depth > 10⁴)	No

Rule of Thumb: Use recursion for trees/graphs, backtracking, and when natural. Convert to iteration if stack overflow is a concern.

Contest tip: On Codeforces, the default stack size is about 256 KB. With each recursive call using roughly 100-200 bytes of stack, you can safely recurse to depth ~10^4. For deeper recursion (graphs with 10^5+ nodes), either use iterative DFS or add #pragma comment(linker, "/STACK:1000000000") on Windows, or submit with a custom stack size on Linux-based judges.

Practice Problems

Beginner (800-1100)

Problem	Concept	Link
Subsets	Basic backtracking	LeetCode 78
Fibonacci	Basic recursion	Classic

Intermediate (1100-1400)

Problem	Concept	Link
Generating Combinations	Combinations	CSES
Permutations	All permutations	CSES
Apple Division	Subset backtracking	CSES

Advanced (1400-1700)

Problem	Concept	Link
N-Queens	Constraint satisfaction	CSES
Grid Paths	Path counting	CSES
Word Search	Backtracking on grid	LeetCode 79

Key Takeaways

Three Parts

Every recursion: base case, recursive case, combine results.

Backtrack = Undo

After recursing, restore state to explore other branches.

Prune Early

Skip invalid branches as soon as possible to avoid TLE.

Watch the Stack

Recursion depth > 10⁴ risks stack overflow on most judges.

Next Up

Chapter 9: Greedy Algorithms

Learn when local optimal choices lead to global optimal solutions—and when they don’t.

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

Recursion & Backtracking

Recursion & Backtracking

The Mental Model

When to Use

Recursion

Backtracking

The Recursion Framework

Pattern 1: Subsets (Power Set)

Pattern 2: Permutations

Pattern 3: Combinations

Pattern 4: Constraint Satisfaction

Pattern 5: Path Finding with Backtracking

The Backtracking Template

Pruning: The Key to Efficiency

Types of Pruning

Common Mistakes

Recursion vs Iteration

Practice Problems

Beginner (800-1100)

Intermediate (1100-1400)

Advanced (1400-1700)

Key Takeaways

Three Parts

Backtrack = Undo

Prune Early

Watch the Stack

Next Up

Chapter 9: Greedy Algorithms

​Recursion & Backtracking

​The Mental Model

​When to Use

Recursion

Backtracking

​The Recursion Framework

​Pattern 1: Subsets (Power Set)

​Pattern 2: Permutations

​Pattern 3: Combinations

​Pattern 4: Constraint Satisfaction

​Pattern 5: Path Finding with Backtracking

​The Backtracking Template

​Pruning: The Key to Efficiency

​Types of Pruning

​Common Mistakes

​Recursion vs Iteration

​Practice Problems

​Beginner (800-1100)

​Intermediate (1100-1400)

​Advanced (1400-1700)

​Key Takeaways

Three Parts

Backtrack = Undo

Prune Early

Watch the Stack

​Next Up

Chapter 9: Greedy Algorithms

Recursion & Backtracking

The Mental Model

When to Use

The Recursion Framework

Pattern 1: Subsets (Power Set)

Pattern 2: Permutations

Pattern 3: Combinations

Pattern 4: Constraint Satisfaction

Pattern 5: Path Finding with Backtracking

The Backtracking Template

Pruning: The Key to Efficiency

Types of Pruning

Common Mistakes

Recursion vs Iteration

Practice Problems

Beginner (800-1100)

Intermediate (1100-1400)

Advanced (1400-1700)

Key Takeaways

Next Up