> ## 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)
</Note>

***

## When to Use

<CardGroup cols={2}>
  <Card title="Recursion" icon="sitemap">
    * Tree/graph traversals
    * Divide and conquer
    * Problems with substructure
    * DP (memoized recursion)
  </Card>

  <Card title="Backtracking" icon="rotate-left">
    * Generate combinations/subsets
    * Permutations
    * Constraint satisfaction (Sudoku, N-Queens)
    * Path finding with constraints
  </Card>
</CardGroup>

***

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

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

<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;
  ```
</Warning>

***

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

***

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

<CardGroup cols={2}>
  <Card title="Three Parts" icon="list-ol">
    Every recursion: base case, recursive case, combine results.
  </Card>

  <Card title="Backtrack = Undo" icon="rotate-left">
    After recursing, restore state to explore other branches.
  </Card>

  <Card title="Prune Early" icon="scissors">
    Skip invalid branches as soon as possible to avoid TLE.
  </Card>

  <Card title="Watch the Stack" icon="layer-group">
    Recursion depth > 10⁴ risks stack overflow on most judges.
  </Card>
</CardGroup>

***

## Next Up

<Card title="Chapter 9: Greedy Algorithms" icon="arrow-right" href="/courses/competitive-programming/09-greedy">
  Learn when local optimal choices lead to global optimal solutions—and when they don't.
</Card>