Week 8: Recursion & Backtracking

1. The Recursion Tree & Base-Case Discipline

A recursive function is one that calls itself on a smaller version of its own input. Every correct recursive function needs two things: at least one base case that returns an answer directly without recursing, and a recursive case whose call always moves strictly closer to a base case. Skip either one and you get infinite recursion, which shows up at runtime as a stack overflow rather than a compile error.

It helps to picture a recursive function's execution as a tree: the root is the original call, and each call's children are the recursive calls it makes. The classic example that makes this visible is naive Fibonacci, where each call branches into two smaller calls:

#include <iostream>
using namespace std;

// Base-case discipline: fib(0) and fib(1) return directly -- no further
// recursion. Every other call reduces n by at least 1, so the recursion
// is guaranteed to reach a base case.
long long fib(int n) {
    if (n <= 1) return n;                 // base cases
    return fib(n - 1) + fib(n - 2);       // recursive case
}

int main() {
    for (int i = 0; i < 10; i++) cout << fib(i) << " ";
    cout << "\n";
}

Each call to fib(n) spawns two more calls until it hits a base case, so the recursion tree has branching factor 2 and height n — that gives roughly 2²​​, precisely O(2ⁿ), total calls, dominated by massive repeated work (fib(5) gets computed inside fib(7) multiple separate times). Time complexity is O(2ⁿ); space complexity is only O(n), because at any instant only one root-to-leaf path of the tree is actually on the call stack — the rest of the tree hasn't been built yet or has already returned.

2. Backtracking for Subsets

Backtracking is recursion with a specific shape: at each step you choose an option, explore forward by recursing with that choice made, and then un-choose it (undo the choice) before trying the next option. That undo step is what lets a single mutable container represent every path through the search tree without allocating a fresh copy at each level.

Generating all subsets of a set is the cleanest illustration: at each index you either exclude the element or include it, so the two branches trace out every possible subset:

#include <vector>
using namespace std;

void backtrack(int idx, vector<int>& nums, vector<int>& current,
               vector<vector<int>>& result) {
    if (idx == (int)nums.size()) {
        result.push_back(current);        // record a completed subset
        return;
    }

    // Choice 1: exclude nums[idx]
    backtrack(idx + 1, nums, current, result);

    // Choice 2: include nums[idx]
    current.push_back(nums[idx]);          // choose
    backtrack(idx + 1, nums, current, result);  // explore
    current.pop_back();                    // un-choose (backtrack)
}

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

There are 2ⁿ subsets of an n-element set, and copying current into result costs up to O(n), so this runs in O(n · 2ⁿ) time. Space is O(n) beyond the output, matching the recursion depth.

3. Backtracking for Permutations

Permutations need a different choice structure than subsets: instead of an include/exclude decision per element, you decide which unused element goes into the current position. A clean way to implement this without extra bookkeeping is to swap the candidate into place, recurse, then swap back:

#include <vector>
using namespace std;

void backtrack(vector<int>& nums, int start, vector<vector<int>>& result) {
    if (start == (int)nums.size()) {
        result.push_back(nums);           // a full permutation
        return;
    }
    for (int i = start; i < (int)nums.size(); i++) {
        swap(nums[start], nums[i]);              // choose: fix nums[i] at position start
        backtrack(nums, start + 1, result);       // explore
        swap(nums[start], nums[i]);              // un-choose: restore original order
    }
}

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

There are n! permutations of n distinct elements, each costing O(n) to copy, so this is O(n · n!) time. When the input can contain duplicates, sort nums first and add a used[] boolean array with a skip-if-already-used-at-this-level check — swapping alone doesn't correctly dedupe permutations with repeated values.

4. N-Queens

N-Queens asks you to place n queens on an n × n board so that no two attack each other — meaning no shared row, column, or diagonal. Placing one queen per row by construction handles the row constraint automatically, so backtracking only needs to track used columns and the two diagonal directions, which you can identify with row - col (one diagonal family) and row + col (the other):

#include <vector>
#include <unordered_set>
using namespace std;

void solve(int row, int n, vector<int>& cols,
           unordered_set<int>& usedCols,
           unordered_set<int>& usedDiag1,   // row - col
           unordered_set<int>& usedDiag2,   // row + col
           vector<vector<int>>& solutions) {
    if (row == n) {
        solutions.push_back(cols);        // cols[r] = column of the queen in row r
        return;
    }
    for (int col = 0; col < n; col++) {
        int d1 = row - col, d2 = row + col;
        if (usedCols.count(col) || usedDiag1.count(d1) || usedDiag2.count(d2))
            continue;                     // pruned: this square is under attack

        cols[row] = col;
        usedCols.insert(col); usedDiag1.insert(d1); usedDiag2.insert(d2);

        solve(row + 1, n, cols, usedCols, usedDiag1, usedDiag2, solutions);

        usedCols.erase(col); usedDiag1.erase(d1); usedDiag2.erase(d2);  // backtrack
    }
}

int countNQueens(int n) {
    vector<vector<int>> solutions;
    vector<int> cols(n, -1);
    unordered_set<int> usedCols, usedDiag1, usedDiag2;
    solve(0, n, cols, usedCols, usedDiag1, usedDiag2, solutions);
    return (int)solutions.size();
}

Without any pruning, trying every column in every row is O(nⁿ). The column/diagonal checks prune enormous portions of the tree in practice — for n = 8 the classic problem, the search explores a tiny fraction of the 64-square placements — though the formal worst-case bound stays exponential.

5. Pruning Search Spaces

Pruning means detecting, as early as possible, that a partial choice can never lead to a valid or optimal solution, and abandoning that branch before recursing into it. N-Queens already pruned via the column/diagonal sets above; a second common pruning trick is sorting the input so that once a candidate is too large, you know every later candidate is too, and can break out of the loop instead of merely continue-ing past one bad option:

#include <vector>
#include <algorithm>
using namespace std;

void backtrack(vector<int>& candidates, int target, int start,
               vector<int>& current, vector<vector<int>>& result) {
    if (target == 0) {
        result.push_back(current);
        return;
    }
    for (int i = start; i < (int)candidates.size(); i++) {
        if (candidates[i] > target) break;   // pruned: sorted, so all later ones are too big too

        current.push_back(candidates[i]);
        // pass i (not i + 1): each candidate can be reused
        backtrack(candidates, target - candidates[i], i, current, result);
        current.pop_back();
    }
}

vector<vector<int>> combinationSum(vector<int> candidates, int target) {
    sort(candidates.begin(), candidates.end());   // sorting is what enables the break-prune
    vector<vector<int>> result;
    vector<int> current;
    backtrack(candidates, target, 0, current, result);
    return result;
}

A third pruning strategy — the most powerful one — is noticing when the same subproblem gets explored more than once with no new information, the way fib(5) got recomputed repeatedly in Section 1. Caching those results (memoization) turns exponential backtracking into polynomial dynamic programming, which is exactly the transition Week 13 makes explicit.

6. Hands-on Exercise

7. Knowledge Check

Four quick questions. Expand each to check your answer.