Complete Search & Backtracking

Quick Revisit

• USE WHEN: n is small enough for brute force (n <= 20 for subsets, n <= 10 for permutations) or pruning cuts the search space drastically
• INVARIANT: Every reachable state is visited exactly once; pruned branches cannot contain valid solutions
• TIME: O(2^n) subsets, O(n!) permutations, often much less with pruning | SPACE: O(n) recursion stack
• CLASSIC BUG: Missing backtrack step (forgetting to undo state changes before trying the next branch)
• PRACTICE: Practice Ladder

Systematically explore every candidate solution, pruning impossible branches early to make brute force fast enough.

Difficulty: Beginner | Prerequisites: Sorting and Searching, Bit Manipulation | CF Rating Range: 1100–1400

---

Contents

• Intuition
• C++ STL Reference
• Implementation
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• When Brute Force IS the Solution
• If I Had 5 Minutes
• Pattern Fingerprint
• Rating Progression
• Before You Code—Checklist
• What Would You Do If...?
• Historical Note
• The Mistake That Teaches
• When NOT to Use Complete Search
• Debug This!
• Further Reading
• Next Up

---

Intuition

Find all subsets of [3, 1, 4, 1, 5] that sum to 8.

There are $2^5=32$ subsets. List them all:

  {}              sum= 0         {3,1,4,1,5}     sum=14
  {5}             sum= 5         {3,1,4,1}       sum= 9
  {1}             sum= 1         {3,1,4,5}       sum=13
  {1,5}           sum= 6         {3,1,1,5}       sum=10
  {4}             sum= 4         {3,4,1,5}       sum=13
  {4,5}           sum= 9         {1,4,1,5}       sum=11
  {4,1}           sum= 5         {3,1,1}         sum= 5
  {4,1,5}         sum=10         {3,4,5}         sum=12
  {1}             sum= 1         {3,4,1}         sum= 8  <-- HIT
  {1,5}           sum= 6         {3,1,5}         sum= 9
  {1,1}           sum= 2         {3,5}           sum= 8  <-- HIT
  {1,1,5}         sum= 7         {1,1,5}         sum= 7
  {3}             sum= 3         {1,4,5}         sum=10
  {3,5}           sum= 8  <--    {1,4,1}         sum= 6
  {3,1}           sum= 4         {3,1,4}         sum= 8  <-- HIT
  {3,1,5}         sum= 9         ...

That works for $n=5$. Now the contest gives you $n=20$. That is $2^{20}=1048576$ subsets—still fine, roughly ${10}^6$. But $n=25$ gives $2^{25}\approx 33$ million, and $n=30$ gives over a billion. The raw enumeration hits TLE fast.

Worse: most of those subsets are obviously hopeless. Once your running sum exceeds 8, every superset of that prefix also exceeds 8. You checked them all anyway.

Build solutions one decision at a time; the moment a partial solution cannot possibly lead to a valid answer, abandon (prune) the entire subtree.

Analogy: You are searching a building for a lost key. You open Room 1—empty. You open a closet inside—empty. Instead of also checking the drawers inside that closet, you back out and try Room 2. If the whole east wing is locked and the key cannot be there, you skip every room in it. Brute force checks every drawer in every room on every floor. Backtracking skips entire wings.

Visual Walkthrough

Same problem: a = [3, 1, 4, 1, 5], target $T=8$. Build subsets by deciding include / skip for each element left to right. Track running sum and remain (sum of elements not yet decided).

  Depth   Decision           Path          sum   remain   Action
  -----   --------           ----          ---   ------   ------
    0      include a[0]=3     3 . . . .      3      11    continue
    1      include a[1]=1     3 1 . . .      4       10   continue
    2      include a[2]=4     3 1 4 . .      8       6    FOUND
    .                                                     sum=T > prune deeper
    .      --- backtrack to depth 2, try skip ---
    2      skip a[2]          3 1 _ . .      4       6    continue
    3      include a[3]=1     3 1 _ 1 .      5       5    continue
    4      include a[4]=5     3 1 _ 1 5     10       0    sum>T > PRUNE
    .      --- backtrack to depth 4, try skip ---
    4      skip a[4]          3 1 _ 1 _      5       0    leaf, sum!=T
    .      --- backtrack to depth 3, try skip ---
    3      skip a[3]          3 1 _ _ .      4       5    continue
    4      include a[4]=5     3 1 _ _ 5      9       0    sum>T > PRUNE
    4      skip a[4]          3 1 _ _ _      4       0    leaf, sum!=T
    .      --- backtrack to depth 1, try skip ---
    1      skip a[1]          3 _ . . .      3       10   continue
    2      include a[2]=4     3 _ 4 . .      7       6    continue
    3      include a[3]=1     3 _ 4 1 .      8       5    FOUND
    .                                                     prune deeper
    .      --- backtrack, skip a[3] ---
    3      skip a[3]          3 _ 4 _ .      7       5    continue
    4      include a[4]=5     3 _ 4 _ 5     12       0    sum>T > PRUNE
    4      skip a[4]          3 _ 4 _ _      7       0    leaf, sum!=T
    .      --- backtrack to depth 2, try skip ---
    2      skip a[2]          3 _ _ . .      3       6    continue
    3      include a[3]=1     3 _ _ 1 .      4       5    continue
    4      include a[4]=5     3 _ _ 1 5      9       0    sum>T > PRUNE
    4      skip a[4]          3 _ _ 1 _      4       0    leaf, sum!=T
    3      skip a[3]          3 _ _ _ .      3       5    continue
    4      include a[4]=5     3 _ _ _ 5      8       0    FOUND
    4      skip a[4]          3 _ _ _ _      3       0    leaf, sum!=T

Three solutions found: {3,1,4}, {3,4,1}, {3,5}.

The search tree as structure (left = include, right = skip):

                              0
                           /     \
                     +3  /         \  skip
                        /           \
                       3             0
                     /   \         /   \
               +1  /       \     /       \
                  /     sk  \   /     sk   \
                 4         3   1           0
               /   \     /   \           /   \
         +4  /   sk \ +4/  sk \        /       \
            /       \ /       \      ...       ...
           8*       4  7       3
          FOUND       / \
          PRUNE     +1/   \sk
                     /     \
                    8*      7
                   FOUND

Node count: brute force visits all 63 tree nodes. Backtracking with pruning visited about 30 nodes here—and the gap widens dramatically as $n$ grows. At $n=20$ with tight pruning, you might visit only a few thousand nodes out of two million.

The Invariant

  +--------------------------------------------------------------+
  |  At every node in the search tree, BOTH conditions hold:     |
  |                                                              |
  |    1. sum <= target                      (feasibility)       |
  |    2. sum + remaining >= target          (reachability)      |
  |                                                              |
  |  If (1) fails: no superset can have sum = target.  PRUNE.   |
  |  If (2) fails: even taking all remaining can not reach T.   |
  |  Both conditions narrow the search tree from both sides.     |
  +--------------------------------------------------------------+

In the walkthrough above, every PRUNE triggers because condition (1) fails—the running sum already exceeds the target. Condition (2) would fire if the target were large relative to the remaining elements (e.g., if sum=3, remain=4, target=8, we know we cannot reach 8 and prune immediately).

What the Code Won't Teach You

The real value of complete search is the insight it generates. Write a brute force, then trace why it's slow, and you'll see it clearly: "This is computing the same subarray sum 1,000 times"—that's the motivation for prefix sums. "This is re-visiting the same state"—that's the motivation for memoization. Complete search is the lens that makes optimizations visible.

  BRUTE FORCE AS A DISCOVERY TOOL:

  Write brute force
       |
       v
  Run on small cases
       |
       v
  Trace WHY it is slow
       |
       +---> "Same subproblem solved repeatedly"  --> DP / memoization
       +---> "Same subarray sum recomputed"        --> prefix sums
       +---> "Same pairs checked redundantly"      --> sorting + two pointers
       +---> "Search space has symmetry"            --> divide by symmetry factor

  The brute force REVEALS the optimization.

Pruning is where the artistry lives. Any brute force can be pruned; the question is which conditions are cheap to check and eliminate large branches. Constraint propagation—if element 0 is assigned to group A, elements 1–k cannot also be in group A—is the key type, and it is also the basis of advanced techniques like constraint programming.

  PRUNING IMPACT -- same problem, different pruning:

  n=20, subset sum target=50

  No pruning:           2^20 = 1,048,576 nodes visited
  Feasibility only:     ~200,000 nodes   (5x speedup)
  Feasibility + reach:  ~15,000 nodes    (70x speedup)
  + sort descending:    ~3,000 nodes     (350x speedup)

  Each layer of pruning compounds.
  Sort input descending --> large items hit bounds sooner
  --> prune entire subtrees early --> massive savings.

Pruning Tree—Annotated Diagram

a = [3, 4, 5, 2], target T = 6. Each node shows the running sum after a take/skip decision. Branches marked # are pruned—the entire subtree below is never visited.

  root: sum=0
  |-- take a[0]=3 --> sum=3
  |   |-- take a[1]=4 --> sum=7 > T  --> # PRUNE (saves 7 nodes below)
  |   |-- skip a[1] --> sum=3
  |       |-- take a[2]=5 --> sum=8 > T --> # PRUNE
  |       |-- skip a[2] --> sum=3
  |           |-- take a[3]=2 --> sum=5 (leaf, != T)
  |           |-- skip a[3] --> sum=3 (leaf, != T)
  |-- skip a[0] --> sum=0
      |-- take a[1]=4 --> sum=4
      |   |-- take a[2]=5 --> sum=9 > T --> # PRUNE
      |   |-- skip a[2] --> sum=4
      |       |-- take a[3]=2 --> sum=6 = T --> * FOUND
      |       |-- skip a[3] --> sum=4 (leaf, != T)
      |-- skip a[1] --> sum=0
          |-- take a[2]=5 --> sum=5
          |   |-- take a[3]=2 --> sum=7 > T --> # PRUNE
          |   |-- skip a[3] --> sum=5 (leaf, != T)
          |-- skip a[2] --> sum=0
              |-- take a[3]=2 --> sum=2 (leaf, != T)
              |-- skip a[3] --> sum=0 (leaf, != T)

  Without pruning: 31 nodes.  With pruning: 20 nodes.
  The first # at depth 2 alone saved 7 nodes.
  At n=20, this compounds to millions of nodes saved.

Complete search + meet-in-the-middle is an important composition. When $n\le 40$, full bitmask enumeration ($2^{40}$) is too slow, but splitting into two halves of 20 elements ($2^{20}+2^{20}=2\times {10}^6$) is fast. The trigger is recognizable: a constraint limit around $n=40$ and a combinable property like sum.

With those deeper insights in hand, here is how to recognize when complete search is the right approach.

When to Reach for This

Trigger phrases in problem statements:

• "Find all / count all / enumerate all configurations..."
• "Is there any subset / permutation / assignment such that..."
• $n\le 20$ (bitmask), $n\le 10$ (permutations), $n\le 40$ (meet-in-the-middle)
• "Minimum number of moves to reach a state" with small state space
• Constraint-satisfaction with few variables (Sudoku, N-Queens style)

Counter-examples—do NOT use complete search:

• $n\le {10}^5$ and the answer involves subsets → think DP or greedy
• The problem has optimal substructure and overlapping subproblems → DP
• "Shortest path" on a large graph → BFS / Dijkstra, not brute DFS

---

C++ STL Reference

Function / Built-in	Header	Description
next_permutation(f, l)	<algorithm>	Rearranges to next lexicographic permutation; returns false when wrapped
prev_permutation(f, l)	<algorithm>	Previous lexicographic permutation
__builtin_popcount(x)	built-in	Count of set bits in unsigned int
__builtin_popcountll(x)	built-in	Count of set bits in unsigned long long
__builtin_ctz(x)	built-in	Count trailing zeros (index of lowest set bit)
__builtin_clz(x)	built-in	Count leading zeros
__gcd(a, b)	built-in	Greatest common divisor
iota(f, l, val)	<numeric>	Fill range with val, val+1, val+2, ...

Bitmask idioms:

// iterate over all subsets of {0..n-1}
for (int mask = 0; mask < (1 << n); mask++) { ... }

// iterate over all submasks of a given mask
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) { ... }

// check if bit i is set
bool has_i = (mask >> i) & 1;

// lowest set bit
int lo = mask & (-mask);

---

Implementation

Minimal Contest Templates

Recursive backtracking—subset sum:

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

int n, target;
int a[25];
vector<vector<int>> solutions;

void solve(int i, int sum, vector<int>& cur) {
    if (sum == target) { solutions.push_back(cur); return; }
    if (i == n || sum > target) return;
    cur.push_back(a[i]);
    solve(i + 1, sum + a[i], cur);
    cur.pop_back();
    solve(i + 1, sum, cur);
}

int main() {
    cin >> n >> target;
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> cur;
    solve(0, 0, cur);
    cout << solutions.size() << "\n";
}

Iterative bitmask enumeration:

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

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    int cnt = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        int s = 0;
        for (int i = 0; i < n; i++)
            if (mask >> i & 1) s += a[i];
        if (s == target) cnt++;
    }
    cout << cnt << "\n";
}

Permutation enumeration:

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

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    iota(p.begin(), p.end(), 1);
    do {
        // process permutation p
    } while (next_permutation(p.begin(), p.end()));
}

Annotated Versions

Recursive backtracking with pruning—explained:

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

int n, target;
int a[25];
int suffix[26];       // suffix[i] = sum of a[i..n-1]
int ans = 0;

void solve(int i, int sum) {
    // --- BASE: found a valid subset ---
    if (sum == target) {
        ans++;
        return;  // all remaining elements > 0, so any superset exceeds target
    }

    // --- PRUNE 1: overshot the target ---
    if (sum > target) return;

    // --- PRUNE 2: ran out of elements ---
    if (i == n) return;

    // --- PRUNE 3: even taking everything remaining can not reach target ---
    if (sum + suffix[i] < target) return;

    // --- BRANCH: include a[i] ---
    solve(i + 1, sum + a[i]);

    // --- BRANCH: exclude a[i] (backtrack is implicit) ---
    solve(i + 1, sum);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> target;
    for (int i = 0; i < n; i++) cin >> a[i];

    // sort descending: larger elements first means we hit the
    // "sum > target" prune sooner, cutting more branches
    sort(a, a + n, greater<int>());

    // precompute suffix sums for reachability pruning
    suffix[n] = 0;
    for (int i = n - 1; i >= 0; i--)
        suffix[i] = suffix[i + 1] + a[i];

    solve(0, 0);
    cout << ans << "\n";
}

N-Queens via backtracking—explained:

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

int n, ans = 0;
// col[c] = 1 if column c is attacked
// d1[d] = 1 if diagonal (row-col+n-1) is attacked
// d2[d] = 1 if anti-diagonal (row+col) is attacked
bool col[20], d1[40], d2[40];

void solve(int row) {
    if (row == n) { ans++; return; }
    for (int c = 0; c < n; c++) {
        // --- CHECK: is this cell safe? ---
        if (col[c] || d1[row - c + n - 1] || d2[row + c]) continue;

        // --- PLACE queen and mark attacks ---
        col[c] = d1[row - c + n - 1] = d2[row + c] = true;
        solve(row + 1);

        // --- BACKTRACK: remove queen, unmark ---
        col[c] = d1[row - c + n - 1] = d2[row + c] = false;
    }
}

int main() {
    cin >> n;
    solve(0);
    cout << ans << "\n";
}

---

Operations Reference

Operation	Time Complexity	Space	Notes
Enumerate all subsets (bitmask)	$O(2^n\cdot n)$	$O(n)$	Inner loop reads bits
Enumerate all subsets (recursive)	$O(2^n)$ nodes visited	$O(n)$	Stack depth $n$
Pruned subset search	$O(2^n)$ worst case	$O(n)$	Often much faster in practice
Enumerate all permutations	$O(n!\cdot n)$	$O(n)$	$n\le 10$ safely
next_permutation (single call)	$O(n)$ amortized	$O(1)$	In-place
N-Queens backtracking	$O(n!)$ worst	$O(n)$	Pruning makes it fast
Meet-in-the-middle	$O(2^{n/2}\cdot n)$	$O(2^{n/2})$	See 16-meet-in-the-middle.md
Iterative deepening DFS	$O(b^d)$	$O(d)$	$b$ = branching, $d$ = depth

Rule of thumb: $2^{20}\approx {10}^6$ (fine), $2^{25}\approx 3\times {10}^7$ (borderline), $10!=3.6\times {10}^6$ (fine), $12!\approx 5\times {10}^8$ (tight).

---

Problem Patterns & Tricks

Subset Enumeration via Bitmask

When: $n\le 20$, need to check all subsets for some property.

  HOW BITMASK MAPS TO SUBSETS (n=4, elements = {A, B, C, D}):

  mask  binary  subset         mask  binary  subset
  ----  ------  ------         ----  ------  ------
   0    0000    {}              8    1000    {D}
   1    0001    {A}             9    1001    {A,D}
   2    0010    {B}            10    1010    {B,D}
   3    0011    {A,B}          11    1011    {A,B,D}
   4    0100    {C}            12    1100    {C,D}
   5    0101    {A,C}          13    1101    {A,C,D}
   6    0110    {B,C}          14    1110    {B,C,D}
   7    0111    {A,B,C}        15    1111    {A,B,C,D}

  Bit i set in mask  <-->  element i is in the subset.
  Total subsets = 2^n = 16 for n=4.

for (int mask = 0; mask < (1 << n); mask++) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        if (mask >> i & 1) sum += a[i];
    // check sum or whatever property
}

Trick: To iterate only over subsets of size exactly $k$, use Gosper's hack:

int mask = (1 << k) - 1;
while (mask < (1 << n)) {
    // process mask (has exactly k bits set)
    int c = mask & (-mask), r = mask + c;
    mask = (((r ^ mask) >> 2) / c) | r;
}

Bitmask vs. Recursive Backtracking—When to Use Which

Aspect	Bitmask (iterative)	Recursive backtracking
Best when	n <= 20, all subsets needed	n <= 25, with pruning
Pruning	Hard to prune mid-mask	Natural pruning points
Code style	Shorter, loop-based	Longer, function-based
Per-node speed	Faster (no call overhead)	Slower (function call stack)
Total speed	Visits all 2^n nodes always	Often visits far fewer (pruning)
DP bridge	Natural fit for bitmask DP	Less natural for memoization

Side by side—count subsets with sum = target:

Iterative bitmask (simple, no pruning):

int count = 0;
for (int mask = 0; mask < (1 << n); mask++) {
    int s = 0;
    for (int i = 0; i < n; i++)
        if (mask >> i & 1) s += a[i];
    if (s == target) count++;
}

Recursive with pruning (prunes early, fewer nodes):

int count = 0;
void solve(int i, int sum) {
    if (sum == target) { count++; return; }
    if (i == n || sum > target) return;
    if (sum + suffix[i] < target) return; // reachability prune
    solve(i + 1, sum + a[i]);  // take
    solve(i + 1, sum);          // skip
}

Rule of thumb: Use bitmask when you need every subset anyway (no pruning opportunity) or when feeding into bitmask DP. Use recursion when constraints allow cutting branches early—it wins on total work despite per-node overhead.

Permutation Generation

When: $n\le 10$, need to try all orderings.

vector<int> p(n);
iota(p.begin(), p.end(), 0);
do {
    // evaluate permutation p
} while (next_permutation(p.begin(), p.end()));

Gotcha: The vector must be sorted initially for next_permutation to produce all $n!$ permutations.

N-Queens / Constraint Satisfaction

When: Place items on a board or assign values to variables under mutual constraints.

Strategy: Assign one variable per recursion level. Maintain sets of "forbidden values" for fast conflict checking. Backtrack on conflict.

Key optimization: Use bitmasks for the forbidden sets. For N-Queens, three integers (cols, diag1, diag2) encode all attacked positions. Checking and updating is $O(1)$.

void solve(int row, int cols, int d1, int d2) {
    if (row == n) { ans++; return; }
    int avail = ((1 << n) - 1) & ~(cols | d1 | d2);
    while (avail) {
        int bit = avail & (-avail);   // lowest available column
        avail ^= bit;
        solve(row + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1);
    }
}

Pruning with Bound Checking

When: Search tree is too large without pruning, but feasibility / optimality bounds exist.

Three fundamental pruning strategies:

1. Feasibility prune: Partial solution already violates a constraint. Abandon.
2. Optimality prune (branch and bound): Best possible extension of current partial solution is worse than the best complete solution found so far. Abandon.
3. Symmetry prune: Current branch is equivalent to one already explored. Skip it.

Template with optimality pruning:

int best = INT_MAX;

void solve(int i, int cost) {
    if (cost >= best) return;          // optimality prune
    if (i == n) { best = cost; return; }
    // try each choice for position i
    for (int c : choices[i]) {
        solve(i + 1, cost + w[c]);
    }
}

Meet-in-the-Middle Connection

When: $n$ up to 40 and you need subset properties (e.g., subset sum).

Split the array in half. Enumerate all $2^{n/2}$ subsets for each half. Combine results with sorting + binary search or two pointers.

This reduces $O(2^{40})\approx {10}^{12}$ to $O(2^{20}\cdot 20)\approx 2\times {10}^7$.

See the full writeup: Meet in the Middle.

  MEET IN THE MIDDLE -- VISUAL:

  Problem: find subset of n=40 elements with sum = T.
  Naive: 2^40 ~ 10^12 subsets.  WAY too slow.

  SPLIT:
  +--------------------+--------------------+
  | Left half (20)     | Right half (20)    |
  | a[0..19]           | a[20..39]          |
  +--------------------+--------------------+
         |                       |
         v                       v
  Enumerate all 2^20      Enumerate all 2^20
  subsets, store sums     subsets, store sums
  in sorted list L        in sorted list R
  (~1M entries)           (~1M entries)
         |                       |
         +----------+------------+
                    |
                    v
         For each sum s in L:
           binary search R for (T - s)
           if found --> answer!

  Total: 2 * 2^20 + 2^20 * log(2^20)
       ~ 2M + 20M = 22M operations.  FAST.

Iterative Deepening DFS (IDDFS)

When: The search tree has unknown or very large depth, but the answer is shallow and BFS would blow up memory.

Run DFS with depth limit $d=0,1,2,\dots$ until a solution is found. Each level is cheap because the tree grows exponentially—the last iteration dominates the total cost.

bool dfs(State s, int depth, int limit) {
    if (is_goal(s)) return true;
    if (depth == limit) return false;
    for (auto next : neighbors(s))
        if (dfs(next, depth + 1, limit)) return true;
    return false;
}

int iddfs(State start) {
    for (int lim = 0; ; lim++)
        if (dfs(start, 0, lim)) return lim;
}

Cost of re-expansion: If the branching factor is $b$ and answer depth is $d$, total work is $O(b^d\cdot b/(b-1))$—only a constant factor more than a single BFS at depth $d$.

Generating Combinations ($n$ choose $k$)

When: Need all subsets of a fixed size $k$.

Worked example—4-Queens with constraint propagation:

  Place 4 queens on a 4x4 board, no two attacking each other.
  Backtrack row by row. Track forbidden columns and diagonals.

  Row 0: try col 0
    +---+---+---+---+      forbidden: cols={0}, d1={0}, d2={0}
    | Q | . | . | . |
    +---+---+---+---+
    | . | . | . | . |      Row 1: col 0 blocked, col 1 blocked (diag)
    +---+---+---+---+             try col 2
    | . | . | . | . |
    +---+---+---+---+      +---+---+---+---+
    | . | . | . | . |      | Q | . | . | . |
    +---+---+---+---+      +---+---+---+---+
                            | . | . | Q | . |  forbidden: cols={0,2}
                            +---+---+---+---+
                            | . | . | . | . |  Row 2: cols 0,1,2,3 all
                            +---+---+---+---+         blocked! BACKTRACK
                            | . | . | . | . |
                            +---+---+---+---+

  Row 1: try col 3 instead
    +---+---+---+---+      Row 2: col 0 blocked, col 3 blocked
    | Q | . | . | . |             try col 1
    +---+---+---+---+
    | . | . | . | Q |      +---+---+---+---+
    +---+---+---+---+      | Q | . | . | . |
    | . | Q | . | . |      +---+---+---+---+
    +---+---+---+---+      | . | . | . | Q |
    | . | . | . | . |      +---+---+---+---+
    +---+---+---+---+      | . | Q | . | . |  Row 3: try col 2
                            +---+---+---+---+    col 0,1,3 blocked
                            | . | . | Q | . |    col 2 ok? diag check...
                            +---+---+---+---+    d1 conflict! BACKTRACK

  Continue backtracking... eventually find:
    +---+---+---+---+
    | . | Q | . | . |      Solution: [1, 3, 0, 2]
    +---+---+---+---+      Nodes visited: ~16 (vs 4! = 24 without pruning)
    | . | . | . | Q |
    +---+---+---+---+
    | Q | . | . | . |
    +---+---+---+---+
    | . | . | Q | . |
    +---+---+---+---+

// Recursive: generate all k-element subsets of {0..n-1}
void comb(int start, int k, vector<int>& cur) {
    if ((int)cur.size() == k) { process(cur); return; }
    if (start == n) return;
    if (n - start < k - (int)cur.size()) return; // not enough left
    cur.push_back(start);
    comb(start + 1, k, cur);
    cur.pop_back();
    comb(start + 1, k, cur);
}

---

Contest Cheat Sheet

  +-------------------------------------------------------------+
  |            COMPLETE SEARCH  --  QUICK REFERENCE              |
  +-------------------------------------------------------------+
  |                                                              |
  |  1. CHECK CONSTRAINTS                                       |
  |     n <= 20  -->  bitmask subsets        O(2^n)              |
  |     n <= 10  -->  all permutations       O(n!)               |
  |     n <= 40  -->  meet in the middle     O(2^(n/2))          |
  |     n <= 15  -->  bitmask DP             O(2^n * n)          |
  |                                                              |
  |  2. PICK APPROACH                                            |
  |     Simple count    -->  iterative bitmask loop              |
  |     Build solution  -->  recursive backtracking              |
  |     All orderings   -->  next_permutation or recursive       |
  |                                                              |
  |  3. ADD PRUNING (in order of effort)                         |
  |     a. Feasibility   : sum > target? return                  |
  |     b. Reachability   : sum + remain < target? return        |
  |     c. Optimality     : cost >= best? return                 |
  |     d. Symmetry       : skip duplicate elements              |
  |     e. Sort input     : descending helps prune sooner        |
  |                                                              |
  |  4. BITMASK CHEAT                                            |
  |     All subsets:      for m in 0..(1<<n)-1                   |
  |     Submasks of m:    for s=m; s>0; s=(s-1)&m                |
  |     Bit i set?        (m >> i) & 1                           |
  |     Lowest bit:       m & (-m)                               |
  |     Pop count:        __builtin_popcount(m)                  |
  |                                                              |
  +-------------------------------------------------------------+

---

Gotchas & Debugging

Common Mistakes

Mistake	Symptom	Fix
Forgot to undo state on backtrack	Wrong answers, states leak between branches	Always undo every mutation after recursive call
Off-by-one in bitmask range	Misses mask = 0 or mask = (1<<n)-1	Loop: mask = 0 to mask < (1 << n)
Using int bitmask when $n>30$	Undefined behavior / overflow	Use long long for $n>30$
next_permutation on unsorted input	Produces fewer than $n!$ permutations	Sort the array first
Not handling duplicate elements	Counts same logical subset multiple times	Sort + skip adjacent duplicates in recursion
Pruning too aggressively	Missing valid solutions	Verify pruning condition on paper before coding
Pruning too late	TLE—pruning exists but fires too deep in the tree	Move feasibility checks as early as possible
Stack overflow at $n=25$	RE / segfault	Increase stack size or switch to iterative bitmask

Edge Cases to Test

• $n=0$ or $n=1$—make sure the base case handles empty input.
• All elements identical—duplicate-handling logic gets exercised.
• Target is 0—the empty subset is a valid answer.
• Target equals the total sum—only the full set works.
• Negative numbers in array—changes pruning direction; the sum > target prune is no longer valid without modification.

Debugging Strategy

1. Print the search tree. Add a debug print at the entry of each recursive call showing depth, current state, and decision. Indent by depth so the tree structure is visible.
2. Count nodes visited. If the count is close to $2^n$, your pruning is not firing—rethink your bounds.
3. Test without pruning first. Get correct answers on small cases with pure brute force, then add pruning one condition at a time and verify answers still match.

#ifdef LOCAL
    // add at top of solve():
    for (int d = 0; d < depth; d++) cerr << "  ";
    cerr << "depth=" << depth << " sum=" << sum << "\n";
#endif

Mental Traps

"Complete search is for beginners."

It isn't. Complete search with good pruning solves a surprising number of hard problems. Expert competitors frame solutions as "generate candidates + filter"—which is complete search at a higher level. The technique is not primitive; only the unoptimized version is.

  WRONG:
    Beginner technique --> skip it --> jump to "clever" solution

  RIGHT:
    Complete search --+--> with pruning: solves hard problems directly
                      |
                      +--> without pruning: still useful as:
                           * correctness oracle for stress testing
                           * discovery tool for finding the DP/greedy
                           * verification of clever solution

"I should immediately think of the clever solution."

The clever solution is usually just a complete search with the right optimizations layered on. Going directly to "clever" means you're guessing at the optimization. Going through brute force first means the optimization reveals itself naturally: what is the brute force doing redundantly?

  WRONG path:
    problem --> "looks like DP" --> guess recurrence --> WA --> stuck

  RIGHT path:
    problem --> write brute force --> trace on small input
       |
       v
    "Why is it slow?"
       |
       +--> "Same state visited twice"     --> add memoization = DP
       +--> "Redundant pair comparisons"   --> sort + two pointers
       +--> "Recomputing sums"             --> prefix sums
       |
       v
    Optimization EMERGES from the brute force.

"If the brute force is O(n^3) and n = 10^5, it's useless."

The brute force is not just about passing the time limit—it's a thinking scaffold. Even if it TLEs, write it. Small cases give you correct answers to check against. Tracing why it's slow tells you exactly what to optimize.

  WRONG:
    "O(n^3) won't pass for n=10^5"  --> don't write it --> no oracle
                                     --> clever solution has subtle bug
                                     --> WA with no way to debug

  RIGHT:
    "O(n^3) won't pass for n=10^5"  --> write it anyway (5 min)
                                     --> run on n <= 50 cases
                                     --> stress test clever solution
                                     --> find the bug --> AC

---

Self-Test

Before moving to practice problems, verify you can do these without looking at the notes above:

• [ ] Write a backtracking solution for "generate all subsets of size $k$ from $n$ elements" with pruning to cut branches when remaining elements can't fill $k$.
• [ ] Explain why writing brute force first—even when you suspect an $O(n^2)$ solution won't pass—is almost always worth the 5 minutes.
• [ ] State the constraint thresholds: when is bitmask enumeration viable? When is permutation enumeration viable?
• [ ] Describe meet-in-the-middle: what problem structure requires it, and what's the time complexity improvement over naive complete search?
• [ ] Name two types of pruning that apply to most backtracking problems.
• [ ] Given next_permutation, explain why forgetting to sort the input first produces fewer than $n!$ permutations.
• [ ] Estimate: $n=18$ with bitmask + $O(n)$ check per mask—how many total operations? Is it feasible?

---

Practice Problems

#	Problem	Source	Rating / Difficulty	Key Technique
1	Apple Division	CSES	Easy	Bitmask subset enumeration
2	Petr and a Combination Lock	CF 1097B	1200	Enumerate all sign assignments
3	Preparing Olympiad	CF 550B	1300	Subset constraints
4	Palindrome Reorder	CSES	Easy	Brute construction check
5	Chessboard and Queens	CSES	Medium	N-Queens backtracking
6	Creating Strings	CSES	Medium	Permutation generation
7	Grid Paths	CSES	Hard	Heavy pruning on 7x7 grid
8	Meet in the Middle	CSES	Hard	Split-half subset sum
9	Beautiful Mirrors	CF 1265E	1700	Complete search with math
10	K-Periodic Garland	CF 1353E	1900	Enumeration with DP pruning

Start with problems 1–3 to build confidence in bitmask and basic backtracking. Problems 5–7 train constraint-based pruning. Problem 8 bridges to Meet in the Middle.

---

When Brute Force IS the Solution

Not every problem needs a clever algorithm. Many contest problems are designed for complete search:

  +--------------------------------------------------------------+
  |  CONSTRAINT --> TECHNIQUE DECISION GUIDE                      |
  +--------------------------------------------------------------+
  |  n <= 8    | Permutations OK: 8! = 40,320                    |
  |  n <= 10   | Permutations with pruning: 10! = 3.6M           |
  |  n <= 20   | Bitmask enumeration: 2^20 ~ 1M                  |
  |  n <= 25   | Bitmask with aggressive pruning                  |
  |  n <= 40   | Meet in the middle (16-meet-in-the-middle.md)   |
  |  any n     | Stress testing: brute force as correctness oracle|
  +--------------------------------------------------------------+

If n fits these bounds and the problem asks "count all / find all / is there any," reach for complete search first. Don't spend 30 minutes hunting for a DP recurrence when $2^n$ fits in time. Many 1200-rated CF problems are pure brute force; read the constraints before designing the algorithm.

---

If I Had 5 Minutes

1. Check constraints—if n ≤ 20, bitmask; if n ≤ 10, permutations.
2. Write the loop—for (mask = 0; mask < (1<<n); mask++).
3. Add the check—extract subset, test property.
4. Consider pruning—feasibility first, then reachability.
5. Sort input descending—free speedup for pruned search.

Brute force tries every key on the keyring. Backtracking skips the entire silver-key pile the moment you see the lock is gold.

---

Pattern Fingerprint

  +--------------------------------------------------------------+
  |  CONSTRAINT FINGERPRINT --> TECHNIQUE                         |
  +--------------------------------------------------------------+
  |  "all subsets" + n <= 20      -->  bitmask loop               |
  |  "all permutations" + n <= 10 -->  next_permutation           |
  |  "assign k items" + k <= 15   -->  bitmask DP                 |
  |  n <= 40 + sum/xor property   -->  meet in the middle         |
  |  "place on board" + small N   -->  backtracking + constraints  |
  |  "minimum moves" + small state-->  BFS or IDDFS               |
  +--------------------------------------------------------------+

See also: Bitmask DP for when subsets combine with optimal substructure.

---

Rating Progression

  +--------------------------------------------------------------+
  |  CF ~1200: Enumerate all subsets, check a simple property.    |
  |    Example: "Any subset summing to S?" with n <= 20           |
  +--------------------------------------------------------------+
  |  CF ~1500: Backtracking with one pruning condition.           |
  |    Example: N-Queens, constrained placement on small board    |
  +--------------------------------------------------------------+
  |  CF ~1800: Multiple pruning layers + meet in the middle.     |
  |    Example: Subset sum with n=40 via split-half approach      |
  +--------------------------------------------------------------+
  |  CF ~2100: Branch-and-bound with tight optimality pruning.   |
  |    Example: TSP on n=20 with bitmask DP hybrid               |
  +--------------------------------------------------------------+

---

Before You Code — Checklist

1. Constraints check: Is 2^n or n! within ~10^8 operations?
2. Input sorted? Sorting descending often improves pruning dramatically.
3. Pruning identified? At least one feasibility prune before coding.
4. State minimal? Pass only what changes (index + running total), not entire arrays.
5. Base cases covered? Empty input, zero target, all-same elements.

---

What Would You Do If...?

Scenario 1: n = 18, find all subsets with XOR = k. Bitmask loop over $2^{18}=\mathrm{262,144}$ subsets. Compute XOR in the inner loop. Under 1 second easily.

Scenario 2: n = 35, find a subset with sum = S. Too large for direct bitmask ($2^{35}\approx 34$ billion). Use meet in the middle: split into halves of 17–18 elements, enumerate each half, and combine with binary search.

Scenario 3: n = 12, find the permutation minimizing some cost.$12!\approx 480$ million—tight. Use branch-and-bound pruning, or switch to bitmask DP at $O(2^{12}\times 12)\approx \mathrm{50,000}$ operations.

---

Historical Note

Backtracking was formalized by Derrick Henry Lehmer in the 1950s, though the technique dates to Gauss's work on the eight-queens problem in 1850. The term "branch and bound" was coined by Land and Doig in 1960 for integer programming—the same prune-by-bound idea applied to optimization.

---

The Mistake That Teaches

Your recursive subset-sum solution works perfectly on small cases and silently gives wrong answers on larger ones. After 20 minutes staring at the pruning logic, you add a debug print—and immediately see it: you forgot to undo visited[i] = true after the recursive call. The state leaks between branches.

// BUGGY: state leaks between branches
void solve(int i, int sum) {
    if (sum == target) { ans++; return; }
    if (i == n) return;
    visited[i] = true;        // mark
    solve(i + 1, sum + a[i]);
    // BUG: missing visited[i] = false;
    solve(i + 1, sum);        // skip branch sees i as visited!
}

Lesson: Every mutation before a recursive call needs a matching undo after it. The call stack is a shared workspace—always clean up.

A useful mnemonic for the whole workflow: CLIP—Constraints, Loop, If-prune, Print.

---

When NOT to Use Complete Search

• n > 25 without meet-in-the-middle structure—$2^{25}$ is borderline; beyond that you need DP or algebraic tricks.
• Optimal substructure + overlapping subproblems—that's DP, not brute force.
• Large state space with short answer—BFS or bidirectional BFS, not DFS.
• The answer is a formula—some counting problems look like enumeration but have closed-form solutions. See Constructive Algorithms.
• n > 12 and you need all permutations—$13!\approx 6$ billion. Consider DP or pruned backtracking instead.

---

Debug This!

Find the bug in each snippet. Answers are below—try first!

Bug 1—Forgotten backtrack:

vector<int> path;
void solve(int i) {
    if (i == n) { process(path); return; }
    path.push_back(a[i]);
    solve(i + 1);              // take branch
    solve(i + 1);              // skip branch -- but path still has a[i]!
}

Bug 2—Off-by-one in bitmask:

for (int mask = 1; mask < (1 << n); mask++) {
    int s = 0;
    for (int i = 0; i < n; i++)
        if (mask >> i & 1) s += a[i];
    if (s == target) ans++;
}
// Misses mask=0 (empty set). If target==0, answer is wrong.

Bug 3—next_permutation on unsorted input:

vector<int> p = {3, 1, 2};
do {
    check(p);
} while (next_permutation(p.begin(), p.end()));
// Only generates {3,1,2} -> {3,2,1} -> done. Missed 4 permutations!

Bug 4—Stack overflow from missing base case:

void solve(int i, int sum) {
    if (sum == target) { ans++; return; }
    if (sum > target) return;
    // BUG: missing "if (i == n) return;" --> a[i] is out-of-bounds
    solve(i + 1, sum + a[i]);
    solve(i + 1, sum);
}

Answers

1. Missing path.pop_back() between the two recursive calls. The skip branch runs with a[i] still in path.
2. Loop starts at mask = 1, skipping mask = 0 (empty set). Fix: for (int mask = 0; ...).
3. Input not sorted. next_permutation generates from current arrangement forward. Fix: sort(p.begin(), p.end()) first.
4. No base case for i == n. Accessing a[i] when i >= n is undefined behavior. Fix: add if (i == n) return;.

---

Further Reading

• Competitive Programmer's Handbook (Laaksonen), Chapter 5: Complete Search—clean explanation of backtracking and pruning.
• CP-Algorithms—Generating all subsequences, Gray code.
• USACO Guide—Complete Search module—excellent graduated problem set.
• Meet in the Middle—the natural next step when $n$ is too large for plain search.
• Divide and Conquer—sometimes confused with backtracking; understand the structural difference.
• Greedy—when one-pass decisions suffice, skip the exponential search.
• Practice Ladder—rated problems for drilling brute force and pruning.

---

Next Up

Constructive Algorithms—when the problem asks you to build a valid object rather than search for one.