Recursion and Backtracking

Quick Revisit

• USE WHEN: "Generate all" + n ≤ 20, or problem has choices at each step with undo
• INVARIANT: Base case stops recursion; each choice is applied, recursed, then undone (the 3 B's: Base, Branch, Backtrack)
• TIME: O(2^n) subsets, O(n!) permutations | SPACE: O(n) recursion depth
• CLASSIC BUG: Forgetting to undo state after recursion (missing pop_back or used[i] = false)
• PRACTICE: ../12-practice-ladders/01-ladder-1100-to-1400.md

Every DFS, every DP transition, every divide-and-conquer algorithm is a recursive function in disguise. This file teaches you to think recursively—to see a problem as a smaller copy of itself—and to prune branches you'll never need. Recursion entered computer science through Alonzo Church's lambda calculus in the 1930s and became practical when John McCarthy's LISP (1958) made recursive function calls a first-class language feature. Backtracking was formalized by Derrick Lehmer in the 1950s for combinatorial enumeration. Think of it as Russian nesting dolls: open one and you find a smaller identical copy inside, until you reach the tiniest solid doll—the base case. The key insight that makes everything click: you don't need to understand the whole recursion tree. You only need to trust that the function solves a smaller version correctly, then combine that result with one local decision. This is inductive thinking—the same skill that makes DP, divide-and-conquer, and tree algorithms click. A useful mnemonic: Base, Branch, Backtrack—the 3 B's. The pattern fingerprint to burn into memory: "generate all" + n ≤ 20 → backtracking.

Difficulty: Beginner | Rating: CF 1100–1400 | Prerequisites: basic C++ (loops, arrays, functions), Complexity Analysis

---

Contents

• Intuition
  • When to Reach for This
• C++ STL Reference
• Implementation (Contest-Ready)
• Complexity Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• What to Solve Next
• Further Reading

---

Intuition

Why Loops Aren't Enough

Generate all subsets of $\{1,2,3\}$. There are $2^3=8$ of them. With loops, you might try:

for (int take1 = 0; take1 <= 1; take1++)
    for (int take2 = 0; take2 <= 1; take2++)
        for (int take3 = 0; take3 <= 1; take3++)
            print_subset(take1, take2, take3);

This works—for $n=3$. Now do it for $n=20$. You'd need 20 nested loops. For general $n$ read from input? Impossible. You can't write a variable number of nested loops.

Recursion solves this. Each recursive call acts like one level of nesting, and the depth adjusts to whatever $n$ happens to be at runtime.

void subsets(int i, int n, vector<int>& cur) {
    if (i == n) {
        // cur holds one complete subset—process it
        for (int x : cur) cout << x << ' ';
        cout << '\n';
        return;
    }
    subsets(i + 1, n, cur);           // skip element i
    cur.push_back(i + 1);
    subsets(i + 1, n, cur);           // take element i
    cur.pop_back();                   // undo the choice
}

Call subsets(0, 3, cur) and you get all 8 subsets. Call subsets(0, 20, cur) and you get all $2^{20}$. Same code.

When to Reach for This

Certain phrases in a problem statement are strong signals for recursion or backtracking. Train yourself to spot them:

Trigger phrase in problem	Likely approach
"generate/print/list all subsets"	Subset enumeration ($n\le 20$)
"generate all permutations"	Permutation enumeration ($n\le 10$)
"find all valid configurations"	Backtracking with constraint pruning
"constraint satisfaction" (Sudoku, N-Queens)	Backtracking, one variable at a time
"n is small" ($n\le 20$)	Brute-force / bitmask enumeration is fine
"try all possibilities"	Complete search—recursion or bitmask
"count/enumerate arrangements"	Recursive enumeration, possibly with memo
"partition into groups with equal sum"	Backtracking with pruning
"place items so that no two conflict"	Constraint backtracking

Rule of thumb: if the search space is exponential but $n$ is small enough that $2^n$ or $n!$ fits in time, reach for recursion. If subproblems overlap, add memoization and you have DP. If the answer only needs one valid configuration (not all), add early termination.

See also the data structure selection guide for choosing between enumeration, greedy, and DP approaches.

The Call Stack, Visualized

Every time you call a function, the computer pushes a frame onto the call stack. When the function returns, the frame is popped. For factorial(4):

factorial(4) calls factorial(3)
factorial(3) calls factorial(2)
factorial(2) calls factorial(1)
factorial(1) hits base case, returns 1

    Call Stack (grows downward)
    +-------------------+
    | factorial(4)      |  <-- pushed first
    +-------------------+
    | factorial(3)      |
    +-------------------+
    | factorial(2)      |
    +-------------------+
    | factorial(1)      |  <-- top of stack (active)
    +-------------------+

    Now it unwinds:

    factorial(1) returns 1   -> pop
    +-------------------+
    | factorial(4)      |
    +-------------------+
    | factorial(3)      |
    +-------------------+
    | factorial(2)      |  <-- returns 2*1 = 2 -> pop
    +-------------------+

    +-------------------+
    | factorial(4)      |
    +-------------------+
    | factorial(3)      |  <-- returns 3*2 = 6 -> pop
    +-------------------+

    +-------------------+
    | factorial(4)      |  <-- returns 4*6 = 24 -> pop
    +-------------------+

    Stack empty. Result: 24

The default stack size is usually 1–8 MB. Each frame costs ~dozens of bytes. Deep recursion ($>{10}^5$ levels) can overflow it. Keep this in mind.

Recursion Is a Tree of Choices

Back to subsets of $\{1,2,3\}$. Each call makes two sub-calls: skip or take the current element. This forms a binary tree:

                        subsets(0, {})
                       /              \
               skip 1 /                \ take 1
                     /                  \
           subsets(1, {})          subsets(1, {1})
            /        \              /          \
      skip 2/     take 2\    skip 2/        take 2\
          /            \        /                \
   sub(2,{})   sub(2,{2})  sub(2,{1})    sub(2,{1,2})
    /    \       /    \      /    \         /      \
   s3    t3    s3    t3    s3    t3       s3      t3
   |      |    |      |    |      |       |        |
  {}    {3}  {2}  {2,3} {1}  {1,3} {1,2} {1,2,3}

There are $2^n$ leaves—one per subset. Every internal node is a function call that makes a binary choice. The tree has depth $n$ and $2^{n+1}-1$ total nodes. This is exactly why generating all subsets is $O(2^n)$.

This picture is the single most important thing on this page. DFS traverses trees. DP fills in trees bottom-up. Divide-and-conquer splits at internal nodes. Every technique you'll learn builds on recursion trees.

What Happens Without a Base Case

void oops(int n) {
    cout << n << '\n';
    oops(n - 1);  // never stops
}

The call stack grows without bound until the OS kills your process:

    +-------------------+
    | oops(5)           |
    +-------------------+
    | oops(4)           |
    +-------------------+
    | oops(3)           |
    +-------------------+
    |      ...          |
    +-------------------+   <-- stack overflow!
    | oops(-999999)     |
    +-------------------+

Every recursive function needs at least one base case—a condition that returns without making another recursive call. For subset generation, the base case is i == n. For factorial, it's n <= 1.

Symptoms of a missing or wrong base case:

• Runtime Error (segfault / stack overflow)
• Time Limit Exceeded (function runs "forever" before crashing)

Backtracking: Pruning Branches You'll Never Need

Generating all possibilities is fine when $2^n$ is small. But many problems have exponential search spaces where most branches are dead ends. Backtracking = recursion + early pruning.

The N-Queens Problem (n = 4): place 4 queens on a 4×4 board so no two attack each other. Place one queen per row, choosing a column.

    Board state:            Columns: 0 1 2 3
    Row 0:  . Q . .        Queen at col 1
    Row 1:  . . . Q        Queen at col 3
    Row 2:  Q . . .        Queen at col 0
    Row 3:  . . Q .        Queen at col 2

    Solution: cols = [1, 3, 0, 2]

The recursion tree tries every column for each row, but prunes immediately when a conflict is detected:

                          row 0
             /       /        \        \
          c0        c1        c2        c3
          |         |          |         |
        row 1     row 1      row 1    row 1
       / | \     / | \      / | \    / | \
     c0 c1 c2  c0 c1 c2  c0 c1 c3  c0 c1 c2
      X  X  |   X  X  X   |  X  X   X  X  |
            |              |                |
          row 2          row 2           row 2
           ...            ...             ...

     X = pruned (queen attacked by previous one)

Recursion Tree for N-Queens (N=4)—Full Trace

Below is the complete search tree. Each level picks a column for that row. Pruned branches show the reason; surviving paths are followed to completion.

  Legend:  [rR,cC] = queen at row R, col C
           X(why)  = pruned branch     * = solution found

  Row 0: try c=0, c=1, c=2, c=3
  +------------+------------+------------+------------+
  |            |            |            |            |
 [r0,c0]    [r0,c1]      [r0,c2]      [r0,c3]
  |            |            |            |
  Row 1       Row 1        Row 1        Row 1
  |            |            |            |
  c0 X col     c0 X diag    c0 [r1,c0]  c0 [r1,c0]
  c1 X diag    c1 X col     c1 X diag    c1 X diag
  c2 X anti    c2 X diag    c2 X col     c2 X anti
  c3 [r1,c3]   c3 [r1,c3]   c3 X diag    c3 X col

Branch [r0,c0]→[r1,c3]:

  [r0,c0]->[r1,c3]
     |
   Row 2: c0 X col/r0   c1 [r2,c1]   c2 X diag/r1   c3 X col/r1
                           |
                         Row 3: c0 X diag/r2
                                c1 X col/r2
                                c2 X diag/r1
                                c3 X col/r1
                                --> dead end, backtrack

Branch [r0,c1]→[r1,c3]:

  [r0,c1]->[r1,c3]
     |
   Row 2: c0 [r2,c0]   c1 X col/r0   c2 X diag/r1   c3 X col/r1
             |
           Row 3: c0 X col/r2
                  c1 X col/r0
                  c2 [r3,c2]  --> * SOLUTION: [1, 3, 0, 2] *
                  c3 X col/r1

Branch [r0,c2]→[r1,c0]:

  [r0,c2]->[r1,c0]
     |
   Row 2: c0 X col/r1   c1 X diag/r1   c2 X col/r0   c3 [r2,c3]
                                                          |
                         Row 3: c0 X col/r1
                                c1 [r3,c1]  --> * SOLUTION: [2, 0, 3, 1] *
                                c2 X col/r0
                                c3 X col/r2

Branch [r0,c3]→[r1,c0]:

  [r0,c3]->[r1,c0]
     |
   Row 2: c0 X col/r1   c1 X diag/r1   c2 [r2,c2]   c3 X col/r0
                                           |
                         Row 3: c0 X col/r1
                                c1 X diag/r2
                                c2 X col/r2
                                c3 X col/r0
                                --> dead end, backtrack

Result: $4^4=256$ potential leaves, but pruning explores only ~16 nodes and finds exactly 2 solutions: [1,3,0,2] and [2,0,3,1].

Without pruning: $4^4=256$ leaf nodes. With pruning: the tree collapses to ~60 nodes. For $n=12$, the difference is ${12}^{12}\approx 8.9\times {10}^{12}$ vs. a few million—the difference between "heat death of the universe" and "runs in milliseconds."

The pruning logic is simple: before placing a queen in column $c$ on row $r$, check that no previously placed queen shares the same column, the same diagonal ($r-c$), or the same anti-diagonal ($r+c$).

bool safe(int r, int c, vector<int>& cols) {
    // loop invariant: no queen in rows 0..i-1 conflicts with (r, c)
    for (int i = 0; i < r; i++) {
        if (cols[i] == c) return false;               // same column
        if (abs(cols[i] - c) == abs(i - r)) return false; // same diagonal
    }
    return true;
}

The Fibonacci Trap and the Bridge to DP

Naive recursive Fibonacci:

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

Draw the call tree for fib(5):

                     fib(5)
                    /      \
               fib(4)      fib(3)
              /     \       /    \
          fib(3)  fib(2) fib(2) fib(1)
          /   \    / \    / \
      fib(2) fib(1) . .  . .
       / \
      .   .

fib(3) is computed twice. fib(2) is computed three times. The tree has $O(2^n)$ nodes—fib(50) takes minutes.

Call Stack Visualization for fib(5)

Watch the call stack grow and shrink as fib(5) executes. Each frame is pushed on a recursive call and popped on return. Notice how deep the stack gets and how the same subproblems reappear:

  Step 1: fib(5) calls fib(4)        Step 2: fib(4) calls fib(3)
  +-------------+                    +-------------+
  | fib(5)      |                    | fib(5)      |
  +-------------+                    +-------------+
  | fib(4)      | <-- top            | fib(4)      |
  +-------------+                    +-------------+
                                     | fib(3)      | <-- top
                                     +-------------+

  Step 3: fib(3) calls fib(2)        Step 4: fib(2) calls fib(1)
  +-------------+                    +-------------+
  | fib(5)      |                    | fib(5)      |
  +-------------+                    +-------------+
  | fib(4)      |                    | fib(4)      |
  +-------------+                    +-------------+
  | fib(3)      |                    | fib(3)      |
  +-------------+                    +-------------+
  | fib(2)      | <-- top            | fib(2)      |
  +-------------+                    +-------------+
                                     | fib(1)      | <-- base! returns 1
                                     +-------------+
                                       ^ max depth = 5 frames

  Step 5: fib(1) returns, fib(2)     Step 6: fib(0) returns 0,
          now calls fib(0)                   fib(2) returns 0+1=1
  +-------------+                    +-------------+
  | fib(5)      |                    | fib(5)      |
  +-------------+                    +-------------+
  | fib(4)      |                    | fib(4)      |
  +-------------+                    +-------------+
  | fib(3)      |                    | fib(3)      | <-- now calls fib(1)
  +-------------+                    +-------------+
  | fib(2)      |                      stack shrinks as frames pop
  +-------------+
  | fib(0)      | <-- base! returns 0
  +-------------+

  ...the pattern continues: stack grows to fib(1), shrinks, grows
  to the RIGHT subtree fib(2), and so on.

  KEY INSIGHT: fib(2) appears 3 times in the tree, so the stack
  grows to depth 3+ for it THREE separate times -- redundant work!

  +-------------+
  | fib(5)      |  With memoization, fib(2) is computed ONCE and
  +-------------+  cached. The 2nd and 3rd calls return instantly
  | fib(3)      |  without pushing any new frames.
  +-------------+
  | fib(2)      | <-- computed once, memo[2] = 1
  +-------------+
    later: fib(2) -> memo hit -> no stack growth!

This repeated expansion is why naive recursion is $O(2^n)$. Memoization collapses the tree into a chain of $O(n)$ unique calls—the bridge from recursion to dynamic programming.

Fix: remember what you've already computed.

int memo[51];
bool seen[51];

int fib(int n) {
    if (n <= 1) return n;
    if (seen[n]) return memo[n];
    seen[n] = true;
    return memo[n] = fib(n - 1) + fib(n - 2);
}

Now each value is computed exactly once. Total calls: $O(n)$. This is memoization—and it is literally top-down dynamic programming. The bottom-up version just fills the array iteratively:

int dp[51];
dp[0] = 0; dp[1] = 1;
// loop invariant: dp[0..i-1] hold correct Fibonacci values
for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];

Same recurrence, same result, no recursion overhead. If you understand memoized recursion, you already understand DP—you just haven't written the loop version yet.

From Recursive DFS to an Explicit Stack

Sometimes recursion depth exceeds the stack limit (e.g., a linear graph with ${10}^6$ nodes). Convert to an explicit stack:

    Recursive:                  Iterative:

    void dfs(int u) {           void dfs(int start) {
        vis[u] = 1;                 stack<int> st;
        for (int v : adj[u])        st.push(start);
            if (!vis[v])            while (!st.empty()) {
                dfs(v);                 int u = st.top(); st.pop();
    }                                   if (vis[u]) continue;
                                        vis[u] = 1;
                                        for (int v : adj[u])
                                            if (!vis[v])
                                                st.push(v);
                                    }
                                }

The logic is identical: push neighbors, pop to visit. The difference is that std::stack lives on the heap (gigabytes available) instead of the call stack (a few megabytes). Use this when $n>{10}^5$ and the graph might be a long chain.

Tail Recursion Note

A recursive call is tail-recursive if it is the very last operation the function performs—nothing happens after the call returns. When this holds, the compiler can reuse the current stack frame instead of pushing a new one, effectively converting recursion into a loop. This is called tail call optimization (TCO).

Tail-recursive factorial:

// Tail-recursive: recursive call is the LAST operation.
// The accumulator carries the partial result forward.
long long fact_tail(int n, long long acc = 1) {
    if (n <= 1) return acc;
    return fact_tail(n - 1, acc * n);  // nothing after this call
}

Non-tail-recursive factorial:

// NOT tail-recursive: multiplication happens AFTER the recursive call returns.
long long fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);  // must multiply after call returns
}

Why it matters: With TCO, fact_tail(1000000) uses $O(1)$ stack. Without it, fact(1000000) uses $O(n)$ stack and likely overflows.

The C++ caveat: The C++ standard does not guarantee TCO. Some compilers (GCC, Clang) perform it at -O2 or higher, but you cannot rely on it in contest environments. If stack depth matters, convert to an explicit loop:

long long fact_iter(int n) {
    long long result = 1;
    for (int i = 2; i <= n; i++)  // loop invariant: result == (i-1)!
        result *= i;
    return result;
}

When to manually convert to iteration:

• Recursion depth exceeds ~${10}^5$ (stack overflow risk)
• The recursive function is naturally tail-recursive (easy conversion)
• You need guaranteed performance regardless of compiler optimization level
• Contest judge uses debug/unoptimized compilation flags

What the Code Won't Teach You

The code examples in this file show you how recursive functions look. What they can't convey is the mental process of designing them. The hard part of recursion is never the syntax—it's identifying what the subproblem is.

Given a problem, ask: what is the first decision? What does a smaller version of this problem look like? Once you answer those two questions, the code writes itself.

For backtracking specifically, the hidden skill is pruning. Unoptimized backtracking is brute-force search—$O(k^n)$ in the worst case. The entire optimization comes from cutting branches early. Adding a single if (invalid) continue; before the recursive call can reduce the search space by orders of magnitude. The difference between a solution that TLEs and one that runs in milliseconds is almost always pruning quality, not algorithmic cleverness.

  Full tree vs pruned tree -- branching factor 3

         *
        /|\
       / | \
      *  *  *
     /|  |  |\
    * *  #  * *
   /|    v  |
  * *  cut  #
  |         v
  #        cut
  v
 cut

  * = node explored    # = pruned branch
  Without pruning: 3^n nodes visited
  With pruning: only a fraction survive

Recursion also sits beneath most "real" algorithms you'll encounter later. DFS on a graph is recursive traversal. DP on trees is bottom-up recursion. Divide-and-conquer splits at internal nodes of a recursion tree. If recursion feels disconnected from those topics, it's because you haven't yet seen it as the shared foundation underneath all of them. Keep this in mind as you move through graphs and trees and DP.

---

With the intuition in place, let's look at the C++ tools you'll use in every recursive implementation.

C++ STL Reference

Recursion and backtracking don't need dedicated library support, but these STL tools show up in almost every implementation:

Function / Feature	Header	What it does	Time
vector::push_back(x)	<vector>	Append element—build current state	Amortized $O(1)$
vector::pop_back()	<vector>	Remove last element—undo last choice	$O(1)$
vector::back()	<vector>	Access last element	$O(1)$
next_permutation(a, a+n)	<algorithm>	Advance to next lexicographic permutation	$O(n)$
prev_permutation(a, a+n)	<algorithm>	Go to previous permutation	$O(n)$
__builtin_popcount(x)	built-in	Count set bits—useful for bitmask subsets	$O(1)$
swap(a, b)	<utility>	Swap two values—used in permutation generation	$O(1)$
stack<T>	<stack>	LIFO container—explicit stack for iterative DFS	push/pop $O(1)$
bitset<N>	<bitset>	Fixed-size bit array—track visited/used states	set/test $O(1)$

Now for the contest-ready templates. Each pattern below has a minimal version (copy-paste into a contest) and an explained version (study first).

---

Implementation (Contest-Ready)

Subset Generation—Minimal

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> cur;

void gen(int i) {
    if (i == n) {
        for (int x : cur) cout << x << ' ';
        cout << '\n';
        return;
    }
    gen(i + 1);
    cur.push_back(i + 1);
    gen(i + 1);
    cur.pop_back();
}

int main() {
    cin >> n;
    gen(0);
}

Subset Generation—Explained

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> cur;  // holds the subset being built

void gen(int i) {
    // Base case: we've decided on every element
    if (i == n) {
        for (int x : cur) cout << x << ' ';
        cout << '\n';
        return;
    }
    // Branch 1: skip element (i+1)
    gen(i + 1);

    // Branch 2: take element (i+1)
    cur.push_back(i + 1);  // choose
    gen(i + 1);             // explore
    cur.pop_back();         // un-choose (backtrack)
}

int main() {
    cin >> n;
    gen(0);  // start deciding from index 0
}

N-Queens Solver—Minimal

#include <bits/stdc++.h>
using namespace std;

int n, cnt = 0;
vector<int> col;
vector<bool> usedCol, usedDiag, usedAnti;

void solve(int r) {
    if (r == n) { cnt++; return; }
    // loop invariant: columns 0..c-1 have been tried for row r
    for (int c = 0; c < n; c++) {
        if (usedCol[c] || usedDiag[r - c + n] || usedAnti[r + c]) continue;
        col.push_back(c);
        usedCol[c] = usedDiag[r - c + n] = usedAnti[r + c] = true;
        solve(r + 1);
        usedCol[c] = usedDiag[r - c + n] = usedAnti[r + c] = false;
        col.pop_back();
    }
}

int main() {
    cin >> n;
    usedCol.assign(n, false);
    usedDiag.assign(2 * n, false);
    usedAnti.assign(2 * n, false);
    solve(0);
    cout << cnt << '\n';
}

N-Queens Solver—Explained

#include <bits/stdc++.h>
using namespace std;

int n, cnt = 0;
vector<int> col;           // col[r] = column of queen in row r
vector<bool> usedCol;      // is column c occupied?
vector<bool> usedDiag;     // is diagonal (r - c + n) occupied?
vector<bool> usedAnti;     // is anti-diagonal (r + c) occupied?

void solve(int r) {
    if (r == n) {          // all queens placed—found a valid solution
        cnt++;
        return;
    }
    for (int c = 0; c < n; c++) {
        // Prune: skip columns/diagonals already attacked
        if (usedCol[c] || usedDiag[r - c + n] || usedAnti[r + c])
            continue;

        // Place queen at (r, c)
        col.push_back(c);
        usedCol[c] = usedDiag[r - c + n] = usedAnti[r + c] = true;

        solve(r + 1);  // recurse to next row

        // Backtrack: remove queen, unmark
        usedCol[c] = usedDiag[r - c + n] = usedAnti[r + c] = false;
        col.pop_back();
    }
}

int main() {
    cin >> n;
    usedCol.assign(n, false);
    usedDiag.assign(2 * n, false);
    usedAnti.assign(2 * n, false);
    solve(0);
    cout << cnt << '\n';  // number of valid placements
}

Permutation Generation—Minimal

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> perm;
vector<bool> used;

void gen() {
    if ((int)perm.size() == n) {
        for (int x : perm) cout << x << ' ';
        cout << '\n';
        return;
    }
    // loop invariant: values 1..i-1 have been tried at this position
    for (int i = 1; i <= n; i++) {
        if (used[i]) continue;
        used[i] = true;
        perm.push_back(i);
        gen();
        perm.pop_back();
        used[i] = false;
    }
}

int main() {
    cin >> n;
    used.assign(n + 1, false);
    gen();
}

Combination Generation (n choose k)—Minimal

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> cur;

void gen(int start) {
    if ((int)cur.size() == k) {
        for (int x : cur) cout << x << ' ';
        cout << '\n';
        return;
    }
    // loop invariant: values start..i-1 have been tried as next element
    for (int i = start; i <= n; i++) {
        cur.push_back(i);
        gen(i + 1);
        cur.pop_back();
    }
}

int main() {
    cin >> n >> k;
    gen(1);
}

Iterative DFS with Explicit Stack

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<bool> vis(n, false);
    stack<int> st;
    st.push(0);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (vis[u]) continue;
        vis[u] = true;
        // process node u here
        for (int v : adj[u])
            if (!vis[v])
                st.push(v);
    }
}

Before you submit, sanity-check the complexity. The table below gives quick feasibility bounds.

---

Complexity Reference

Use this table to quickly check time and space costs when deciding whether a recursive approach fits within the problem's constraints:

Operation	Time	Space	Notes
Generate all subsets	$O(2^n)$	$O(n)$ stack	$n\le 20$ in practice
Generate all permutations	$O(n!\cdot n)$	$O(n)$ stack	$n\le 10$ (10! = 3.6M)
Generate combinations $(\genfrac{}{}{0ex}{}{n}{k})$	$O((\genfrac{}{}{0ex}{}{n}{k})\cdot k)$	$O(k)$ stack	Feasible when $(\genfrac{}{}{0ex}{}{n}{k})\le {10}^7$
N-Queens (count solutions)	$O(n!)$ worst case	$O(n)$	With pruning, much faster
Bitmask subset enumeration	$O(2^n)$	$O(1)$	Use for (int m = 0; m < (1<<n); m++)
Memoized recursion (Fibonacci)	$O(n)$	$O(n)$	Each state computed once
Recursive DFS on graph	$O(V+E)$	$O(V)$ stack	Same as iterative DFS

For deeper treatment of how to analyze recursive complexity, see Complexity Analysis.

---

Problem Patterns & Tricks

Recognizing which pattern a problem fits is half the battle. Here are the six most common shapes.

Generate All Subsets

Enumerate all $2^n$ subsets. Two approaches: recursive (include/exclude) and bitmask (for (int m = 0; m < (1 << n); m++)). Use bitmask when $n\le 20$ and you want compact code; use recursive when you need pruning.

// Bitmask approach
// loop invariant: subsets 0..m-1 have been printed
for (int m = 0; m < (1 << n); m++) {
    // loop invariant: bits 0..i-1 of m have been checked
    for (int i = 0; i < n; i++)
        if (m >> i & 1) cout << a[i] << ' ';
    cout << '\n';
}

Problems:

• CF 550B -- Preparing Olympiad—subset sum with constraints ($n\le 15$)
• CSES -- Apple Division—partition into two subsets minimizing difference

Generate All Permutations

Try all $n!$ orderings. Either build your own recursive generator or use next_permutation from <algorithm>.

// STL shortcut
sort(a.begin(), a.end());
do {
    // process permutation
} while (next_permutation(a.begin(), a.end()));

Problems:

• CSES -- Creating Strings—generate all distinct permutations of a string
• CF 432C -- Prime Swaps

Constraint Satisfaction (N-Queens Style)

Place items on a grid or graph subject to constraints. Recurse on each slot, prune when a constraint is violated.

Pattern: decide one variable at a time, check constraints eagerly, undo on backtrack.

Problems:

• CSES -- Chessboard and Queens—N-Queens with blocked cells
• CF 1st Round -- Sudoku

Combination Sum / Subset Sum

Find subsets whose sum equals a target. Prune branches where the partial sum already exceeds the target.

void solve(int i, int remain, vector<int>& cur) {
    if (remain == 0) { record(cur); return; }
    if (i == n || remain < 0) return;
    // take a[i]
    cur.push_back(a[i]);
    solve(i + 1, remain - a[i], cur);
    cur.pop_back();
    // skip a[i]
    solve(i + 1, remain, cur);
}

Problems:

• CSES -- Two Sets
• CF 1829D -- Gold Rush

Partitioning into Groups

Split $n$ items into $k$ groups with constraints (equal sum, limited size, etc.). Recurse: assign each item to one of $k$ groups, prune early.

Problems:

• CSES -- Apple Division
• CF 1593D1 -- Half of Same

Flood Fill / Connected Components (Recursive DFS)

Classic graph traversal. Visit a cell, mark it, recurse on all unvisited neighbors. Convert to iterative if the grid is large.

void flood(int r, int c, vector<vector<char>>& grid) {
    if (r < 0 || r >= n || c < 0 || c >= m) return;
    if (grid[r][c] != '.') return;
    grid[r][c] = '#';
    flood(r+1,c,grid); flood(r-1,c,grid);
    flood(r,c+1,grid); flood(r,c-1,grid);
}

Problems:

• CSES -- Counting Rooms
• CF 1365D -- Solve The Maze

---

Contest Cheat Sheet

If I Had 5 Minutes

1. Template: base case → for each choice → prune → apply → recurse → undo
2. Limits: subsets $n\le 20$, permutations $n\le 10$, backtracking $n\le 15$ with good pruning
3. #1 bug: forgetting to undo state after recursion (pop_back, used[i] = false)
4. Memoization bridge: if you see repeated subproblems in your recursion tree, add a memo table → instant DP
5. Stack overflow? Convert to iterative with std::stack when depth $>{10}^5$

+------------------------------------------------------------------+
|                 RECURSION & BACKTRACKING CHEAT SHEET             |
+------------------------------------------------------------------+
| PATTERN            | TIME         | SPACE  | MAX n (2s TL)       |
|--------------------|--------------|--------|---------------------|
| All subsets        | O(2^n)       | O(n)   | n <= 20             |
| All permutations   | O(n! * n)    | O(n)   | n <= 10             |
| N-Queens           | O(n!)        | O(n)   | n <= 15 (pruned)    |
| Combinations C(n,k)| O(C(n,k))   | O(k)   | C(n,k) <= 10^7     |
| Memoized recur.    | O(states)    | O(st.) | states <= 10^7      |
| DFS (graph)        | O(V+E)       | O(V)   | V,E <= 10^6         |
+------------------------------------------------------------------+
| TEMPLATE:                                                        |
|   void solve(int i, state) {                                     |
|       if (base_case) { process(); return; }                      |
|       for (choice : options) {                                   |
|           if (!valid(choice)) continue;   // PRUNE               |
|           apply(choice);                  // CHOOSE              |
|           solve(i + 1, new_state);        // EXPLORE             |
|           undo(choice);                   // UN-CHOOSE           |
|       }                                                          |
|   }                                                              |
+------------------------------------------------------------------+
| WHEN TO USE:                                                     |
|   - "print/count all ..."  -> full enumeration                   |
|   - "find any valid ..."   -> backtracking with early return     |
|   - Small n (<=20) with exponential constraint -> brute force OK |
|   - Repeated subproblems   -> add memo -> becomes DP             |
+------------------------------------------------------------------+

---

Gotchas & Debugging

Forgetting the base case. Infinite recursion → stack overflow → Runtime Error. Always write the base case first, then the recursive calls.

Not undoing state changes (the #1 backtracking bug). If you push_back before recursing, you must pop_back after. If you set used[i] = true, you must set used[i] = false. Every "choose" needs an "un-choose."

// WRONG                        // RIGHT
cur.push_back(x);              cur.push_back(x);
solve(i + 1);                  solve(i + 1);
// forgot pop_back!            cur.pop_back();

Passing large objects by value.void solve(vector<int> v) copies the entire vector on every call. With $2^n$ calls, this is catastrophic. Pass by reference: void solve(vector<int>& v).

Off-by-one in recursion depth. If elements are 1-indexed but your recursion starts at 0, or vice versa, you'll generate wrong subsets or miss the last element. Match your base case to your indexing.

Stack overflow on deep recursion. For recursive DFS on a graph with ${10}^6$ nodes, a long chain blows the stack. Two fixes:

• Convert to iterative with std::stack.
• Increase stack size: ulimit -s unlimited (Linux) or add a pragma:

  #pragma comment(linker, "/STACK:1000000000")  // MSVC

Generating duplicates. When generating combinations from a multiset, skip duplicate elements at the same recursion level:

for (int i = start; i < n; i++) {
    if (i > start && a[i] == a[i - 1]) continue;  // skip duplicates
    // ...
}

Confusing "subsets" with "subsequences". Subsets don't care about order ($\{1,3\}=\{3,1\}$). Subsequences preserve relative order. For subsets, use include/exclude. For subsequences maintaining order, iterate left-to-right only.

Mental Traps

Tracing instead of trusting. The most common recursion failure mode: you try to mentally trace what solve(5) does by following it into solve(4) into solve(3) and so on. This works for tiny inputs and falls apart for anything real. Your brain runs out of "stack frames" just like the computer does.

The correct approach: assume solve(n-1) returns the correct answer, and show that solve(n) is correct given that assumption. Trust the induction.

  WRONG approach              RIGHT approach

  solve(5)                    solve(n)
    |                           |
    v                           v
  solve(4)                    assume solve(n-1)
    |                         is CORRECT
    v                           |
  solve(3)                      v
    |                         combine with
    v                         local work
  solve(2)                      |
    |                           v
    v                         solve(n) is correct
  solve(1)
    |
    v
  "uhh..."

Conflating recursion with backtracking. Recursion is a control flow mechanism—a function calling itself. Backtracking is a search strategy that uses recursion but specifically involves trying choices and undoing them.

A recursive factorial is not backtracking. A recursive Fibonacci is not backtracking. Backtracking appears when you have a space of choices, and you apply-recurse-undo.

  RECURSION only             BACKTRACKING
  +-----------+              +----------------+
  | f(n)      |              | solve(state)   |
  |  |        |              |  for choice    |
  |  v        |              |   apply -----+ |
  | f(n-1)    |              |   recurse    | |
  |  |        |              |   undo <-----+ |
  |  v        |              |  prune if bad  |
  | f(0)      |              +----------------+
  +-----------+
  No choices to undo         Choices applied
  No branching search        then reversed

Thinking memoization always applies. Memoization works only when the function is pure—same inputs always produce same outputs, no side effects.

Backtracking that mutates global state (a used[] array, a board) cannot be memoized without carefully encoding all relevant state into the memo key. If your function's behavior depends on state outside its parameters, memoization gives wrong answers.

  Memoizable              NOT memoizable

  f(n) ---+               solve(row)
          |                  |
          v                  v
  depends ONLY on n       depends on row AND
  same n --> same result  global board state
          |                  |
          v                  v
  memo[n] = answer        memo[row] = ???
                          board changes between calls

---

Self-Test

• [ ] Write a recursive function to generate all permutations of [1..n] using the apply-recurse-undo pattern, from memory, without any reference.
• [ ] Explain in one sentence why tracing a recursive call tree to verify correctness is inferior to the inductive proof approach.
• [ ] Name two situations where a backtracking solution needs explicit undo logic and one where it doesn't (hint: mutable shared state vs. immutable local state).
• [ ] State the approximate maximum safe recursion depth for a typical competitive programming judge with default stack size.
• [ ] Given a new problem, identify whether it needs subset enumeration, permutation enumeration, or constraint-satisfaction backtracking—and state the maximum feasible $n$ for each.
• [ ] Explain why backtracking with global state mutation cannot be trivially memoized, and what you would need to change to make it memoizable.
• [ ] Convert a simple recursive DFS into an iterative version using an explicit stack, and explain when this conversion is necessary.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Apple Division	CSES	Easy	Enumerate all subsets, minimize difference ($n\le 20$)
2	Creating Strings	CSES	Easy	Generate all distinct permutations
3	Chessboard and Queens	CSES	Easy-Med	N-Queens with blocked squares
4	Counting Rooms	CSES	Easy	Flood fill / recursive DFS on a grid
5	Preparing Olympiad	CF 550B	Easy-Med	Subset enumeration with sum constraints
6	Gold Rush	CF 1829D	Easy-Med	Recursive check: can we reach target by splitting?
7	Grid Paths	CSES	Medium	Backtracking with heavy pruning on a 7×7 grid
8	Solve The Maze	CF 1365D	Medium	DFS/BFS + blocking cells
9	Letter Combinations of a Phone Number	LeetCode 17	Medium	Backtracking over small choice sets
10	Beautiful Arrangement	LeetCode 526	Medium	Permutation with constraint pruning ($n\le 15$)

---

What to Solve Next

Once you're comfortable with the patterns above, your next steps depend on which direction pulls you:

• Memoization feels natural? Move to DP Thinking Framework—top-down recursion with memo is literally DP.
• Bitmask subsets click? Jump to Bitmask DP—encode subset state as an integer and memoize over it.
• DFS on grids/graphs interests you? Continue to Graph and Tree Intro—recursive DFS is the backbone of graph traversal.
• Want more drill? Work through the 1100–1400 practice ladder for contest-rated problems that use these ideas.
• Choosing between techniques? The data structure selection guide helps you decide when brute force is enough vs. when you need something smarter.

---

Further Reading

• Competitive Programmer's Handbook, Ch. 5—Complete Search—free PDF, covers all brute-force methods
• cp-algorithms: Generating Permutations—iterative and recursive approaches
• USACO Guide—Complete Search—excellent beginner walkthrough with practice problems
• CF Blog—Backtracking and Pruning—community discussion of pruning strategies
• In this repo: Complexity Analysis—how to estimate whether your recursive solution will TLE
• In this repo: Bitmask DP—when your memoized recursion state is a bitmask
• In this repo: Graph and Tree Intro—visual dictionary of graph & tree vocabulary (DFS on trees uses recursion)