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.

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ⁿ subsets of an array. Approach: For each element, make two choices: include it or don’t.

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.

vector<vector<int>> combinations(int n, int k) {
    vector<vector<int>> result;
    vector<int> current;
    
    function<void(int)> backtrack = [&](int start) {
        // Found valid combination
        if (current.size() == k) {
            result.push_back(current);
            return;
        }
        
        // Pruning: not enough elements left
        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 avoid duplicates
            current.pop_back();
        }
    };
    
    backtrack(1);
    return result;
}

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.

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result;
    vector<string> board(n, string(n, '.'));
    
    // Track which columns and diagonals are under attack
    vector<bool> cols(n), diag1(2 * n), diag2(2 * n);
    
    function<void(int)> backtrack = [&](int row) {
        if (row == n) {
            result.push_back(board);
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (cols[col] || diag1[row - col + n] || diag2[row + col]) {
                continue;  // Position under attack
            }
            
            // Place queen
            board[row][col] = 'Q';
            cols[col] = diag1[row - col + n] = diag2[row + col] = true;
            
            backtrack(row + 1);
            
            // Remove queen (backtrack)
            board[row][col] = '.';
            cols[col] = diag1[row - col + n] = diag2[row + col] = false;
        }
    };
    
    backtrack(0);
    return result;
}

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.

Types of Pruning

Constraint Pruning: Skip choices that violate constraints
Bound Pruning: Skip if current path can’t lead to better solution
Symmetry Pruning: Skip symmetric configurations

// 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.

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

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

​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