Recursion and Backtracking
How recursion uses the call stack, how to design base cases and progress, and the choose–explore–undo framework that generates subsets, permutations and constraint solutions with pruning.
What you will learn
How recursion uses the call stack, how to design base cases and progress, and the choose–explore–undo framework that generates subsets, permutations and constraint solutions with pruning.
Prerequisites: Modules 2 and 8.
Recursion essentials
Base case, recursive case, progress measure, call stack, recursion tree, stack overflow, tail recursion, and memoization.
Every recursive function needs (1) a base case that returns without recursing, (2) a recursive case that makes the problem strictly smaller, and (3) a measure that decreases on each call — otherwise it never terminates. Each active call keeps a stack frame, so recursion depth is part of the space cost.
Backtracking framework
Choose → explore → undo. Identify state, choices, constraints, pruning rules, and completion conditions.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
#include <bits/stdc++.h>
using namespace std;
void subsets(const vector<int>& a, size_t i, vector<int>& cur, vector<vector<int>>& out) {
if (i == a.size()) { out.push_back(cur); return; }
subsets(a, i + 1, cur, out); // exclude a[i]
cur.push_back(a[i]); // choose
subsets(a, i + 1, cur, out); // explore
cur.pop_back(); // undo
}
// subsets of a multiset without duplicate results: sort, then skip equal siblings
void subsetsDedup(const vector<int>& a, size_t start, vector<int>& cur, vector<vector<int>>& out) {
out.push_back(cur);
for (size_t i = start; i < a.size(); ++i) {
if (i > start && a[i] == a[i - 1]) continue; // same value at the same tree level
cur.push_back(a[i]); subsetsDedup(a, i + 1, cur, out); cur.pop_back();
}
}
void permutations(vector<int>& a, size_t k, vector<vector<int>>& out) {
if (k == a.size()) { out.push_back(a); return; }
for (size_t i = k; i < a.size(); ++i) { swap(a[k], a[i]); permutations(a, k + 1, out); swap(a[k], a[i]); }
}
void combinationSum(const vector<int>& c, size_t start, int remain, vector<int>& cur, ve
…subsets of {1,2,3}: {} {3} {2} {2,3} {1} {1,3} {1,2} {1,2,3}
distinct subsets of {1,2,2}: {} {1} {1,2} {1,2,2} {2} {2,2}
permutations: {1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,2,1} {3,1,2}
combination sum to 7 from {2,3,6,7}: {2,2,3} {7}Core problems
Factorial, Fibonacci, power, array/string recursion, subsets, subsequences, permutations, combinations, combination sum, N-Queens, Sudoku solver, maze paths, word search, palindrome partitioning, and graph coloring.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Placing one queen per row and marking attacked columns and diagonals (row − col and row + col are constant along the two diagonal directions) prunes almost the entire nⁿ space: the 8-queens search visits about two thousand nodes instead of 16.7 million.
#include <bits/stdc++.h>
using namespace std;
int n, nodes;
vector<int> col;
vector<bool> usedCol, usedDiag, usedAnti;
int solve(int row) {
++nodes;
if (row == n) return 1;
int count = 0;
for (int c = 0; c < n; ++c) {
if (usedCol[c] || usedDiag[row - c + n - 1] || usedAnti[row + c]) continue; // prune: attacked square
usedCol[c] = usedDiag[row - c + n - 1] = usedAnti[row + c] = true; col[row] = c;
count += solve(row + 1);
usedCol[c] = usedDiag[row - c + n - 1] = usedAnti[row + c] = false;
}
return count;
}
int main() {
for (int size : {4, 6, 8, 10}) {
n = size; nodes = 0;
col.assign(n, -1); usedCol.assign(n, false); usedDiag.assign(2 * n - 1, false); usedAnti.assign(2 * n - 1, false);
int s = solve(0);
cout << "N=" << n << ": " << s << " solutions, " << nodes << " search nodes (n^n would be " << (long long)pow(n, n) << ")\n";
}
n = 4; nodes = 0; col.assign(4, -1); usedCol.assign(4, false); usedDiag.assign(7, false); usedAnti.assign(7, false);
function<bool(int)> first = [&](int row) -> bool {
if (row == n) return true;
for (int c = 0; c < n; ++c) {
…N=4: 2 solutions, 17 search nodes (n^n would be 256)
N=6: 4 solutions, 153 search nodes (n^n would be 46656)
N=8: 92 solutions, 2057 search nodes (n^n would be 16777216)
N=10: 724 solutions, 35539 search nodes (n^n would be 10000000000)
.Q..
...Q
Q...
..Q.Advanced techniques
Branch and bound, constraint propagation, symmetry breaking, bitmask state, memoized backtracking, exact-cover overview, and pruning with admissible bounds.
Symmetry breaking: for N-Queens, try only first-row columns in the left half and double the count (handle the middle column separately for odd n).
Bitmask state: replace the three boolean arrays with three integers; free columns are ~(cols | diag | anti) & full, and x & -x picks the next one.
Exact cover: Sudoku and N-Queens can be phrased as choosing rows of a 0/1 matrix covering every column exactly once; Knuth's Algorithm X with “dancing links” solves such problems efficiently.
Required lesson output
For each problem, show recursion tree, state variables, base cases, duplicate handling, complexity, and why pruning is correct.
Why pruning is safe index i, current subset sort + skip equal siblings no pruning; every leaf is an answer prefix length k use a frequency count or skip equal swaps start index, remaining target start from i (not 0) to avoid reorderings candidates sorted, so if c[i] > remain all later ones are too row, used columns/diagonals well below n! in practice an attacked square can never lead to a valid board
Quiz
? What does the “undo” step in backtracking do?
+ Restores the state so the next choice starts from the same situation :: Shared mutable state must be put back.
- Frees memory :: Not its purpose.
- Prints the answer :: No.
- Skips duplicates :: That is a separate rule.
? For distinct subsets of {1,2,2}, why skip `a[i] == a[i−1]` only when `i > start`?
+ Equal values must not start two branches at the same level, but the second 2 may follow the first deeper down. :: That yields {2,2} once and {2} once.
- To skip all duplicates entirely :: That would lose {1,2,2}.
- To sort the input :: Sorting is done beforehand.
- It has no effect :: Without it {1,2} and {2} appear twice.
? Why does N-Queens index the diagonals with `row − col` and `row + col`?
+ Each is constant along one diagonal direction, so one boolean per diagonal suffices. :: O(1) attack checks.
- To save time sorting :: No sorting.
- They are the queen's coordinates. :: They identify diagonals.
- It is required by C++. :: No.