> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Recursion & Backtracking

> Master the art of breaking problems into subproblems and exploring all possibilities systematically

# 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."

> [!NOTE]
>
> **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:

```cpp theme={null}
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
```

```cpp theme={null}
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](https://codeforces.com/problemset/problem/264/B) |

***

## Pattern 2: Permutations

**Problem**: Generate all n! permutations.

**Approach**: Fix each element at the current position, recurse for the rest.

```cpp theme={null}
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**

```cpp theme={null}
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.

```cpp theme={null}
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.

```cpp theme={null}
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.

```cpp theme={null}
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

```cpp theme={null}
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

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

```cpp theme={null}
// 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

> [!WARNING]
>
> **Mistake 1: Forgetting to Backtrack**
>
> ```cpp theme={null}
> // 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
> ```

> [!WARNING]
>
> **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

> [!WARNING]
>
> **Mistake 3: Wrong Base Case**
> The base case must handle the smallest valid input:
>
> ```cpp theme={null}
> // 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.

> [!TIP]
>
> **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](https://leetcode.com/problems/subsets/) |
| Fibonacci | Basic recursion | Classic |

### Intermediate (1100-1400)

| Problem | Concept | Link |
| - | - | - |
| Generating Combinations | Combinations | [CSES](https://cses.fi/problemset/task/1622) |
| Permutations | All permutations | [CSES](https://cses.fi/problemset/task/1070) |
| Apple Division | Subset backtracking | [CSES](https://cses.fi/problemset/task/1623) |

### Advanced (1400-1700)

| Problem | Concept | Link |
| - | - | - |
| N-Queens | Constraint satisfaction | [CSES](https://cses.fi/problemset/task/1624) |
| Grid Paths | Path counting | [CSES](https://cses.fi/problemset/task/1625) |
| Word Search | Backtracking on grid | [LeetCode 79](https://leetcode.com/problems/word-search/) |

***

## 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](https://resources.devweekends.com/courses/competitive-programming/09-greedy.md)**
>
> Learn when local optimal choices lead to global optimal solutions—and when they don't.


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.