LC Patterns — Backtracking

void bt(State& path, Choices at this level, Results& out) {
    if (isComplete(path)) { out.push_back(path); return; }   // COPY the path into results
    for (choice : validChoices()) {                          // prune here, not at the leaf
        apply(choice, path);          // choose
        bt(path, next, out);          // explore
        undo(choice, path);           // unchoose — mirror image of apply
    }
}

1. Broken undo symmetry: every apply needs exactly one undo on every exit path — an early continue/return between them silently corrupts all later branches. Structure it so choose/undo hug the recursive call with nothing between.
2. Aliasing on record: out.push_back(path) copies (good — C++ copies by value here); storing references or moving the live path records garbage. Conversely, passing path by value into recursion "works" but costs O(n) per node — pass by reference + undo; say the trade-off.
3. Same-level dedup vs same-path reuse: i > start && a[i] == a[i-1] skips duplicates across siblings (after sorting) while still allowing [1,1,2]-style multi-use within one path. Writing i > 0 instead kills legitimate paths — the classic subtle wrong answer (90/40/47 all test it).
4. start-index vs used[] confusion: a start index ⇒ combinations (each element considered once, order canonical); used[] ⇒ permutations (all orderings). Mixing them either duplicates output or misses it.
5. Complexity statements: subsets O(2ⁿ·n), permutations O(n!·n), combinations O(C(n,k)·k) — the ·n is the copy cost per solution. Say these unprompted; "exponential, and that's optimal because the output is exponential" is the senior framing.
6. Recursion depth & global state: depth ≤ n (fine); shared mutable state (board, column flags) must be undone, not copied — that's the whole point of backtracking over brute-force regeneration.

What it is: Enumerate every subset of a set: at each element either include it or not (a binary decision tree), or equivalently — at each level, pick which next element to add from start onward and record every node, not just the leaves.

Intuition: Two mental models give identical output: include/exclude (each element = one binary choice → 2ⁿ leaves) and start-index growth (every node of the tree is a subset; the loop for i in [start, n) extends the current subset in canonical order — no duplicates because you never look backward). Learn both; the start-index one generalizes to every pattern below. With duplicate inputs (90): sort + same-level skip (§0.3).

Approach:

void bt(vector<int>& a, int start, vector<int>& path, vector<vector<int>>& out) {
    out.push_back(path);                          // record EVERY node — subsets, not leaves
    for (int i = start; i < (int)a.size(); ++i) {
        if (i > start && a[i] == a[i-1]) continue; // dedup (needs sorted input; for 90)
        path.push_back(a[i]);
        bt(a, i + 1, path, out);
        path.pop_back();
    }
}

What it is: All ways to choose k items from n — the subsets tree cut at exactly size k. The start-index discipline keeps each combination in canonical order, so {1,2} and {2,1} are one branch, not two.

Intuition: Combinations = subsets + a size target, which unlocks the signature prune: if the remaining pool can't fill the quota, stop — if (n - i + 1 < k - path.size()) break;. Because the loop goes ascending, break (not continue) kills all further siblings at once. This "count the remaining budget" prune generalizes: sum-based problems prune on the remaining target (Pattern 3), boards prune on constraint flags (Pattern 7).

Approach:

void bt(int n, int k, int start, vector<int>& path, vector<vector<int>>& out) {
    if ((int)path.size() == k) { out.push_back(path); return; }
    for (int i = start; i <= n - (k - (int)path.size()) + 1; ++i) {  // feasibility prune in the bound
        path.push_back(i);
        bt(n, k, i + 1, path, out);
        path.pop_back();
    }
}

What it is: Find combinations summing to a target, under a reuse rule: elements reusable unlimited times (39 — recurse with i, not i+1), or each element used once with duplicate values in the input (40 — recurse i+1 + same-level dedup). The recursion carries remaining = target − chosen so far.

Intuition: The single index passed downward encodes the reuse policy: i = "may pick me again", i+1 = "move on" — one character switches the problem. Sorting buys the strong prune: once a[i] > remaining, every later candidate is too big → break. This family is the cleanest place to see the DP boundary: counting these combinations is coin-change; listing them is irreducibly exponential — same tree, different question.

Approach:

void bt(vector<int>& a, int start, int rem, vector<int>& path, vector<vector<int>>& out) {
    if (rem == 0) { out.push_back(path); return; }
    for (int i = start; i < (int)a.size() && a[i] <= rem; ++i) {   // sorted ⇒ break via loop cond
        if (i > start && a[i] == a[i-1]) continue;                 // for 40 (dups, single use)
        path.push_back(a[i]);
        bt(a, /*39:*/ i /*40: i+1*/, rem - a[i], path, out);
        path.pop_back();
    }
}

What it is: All orderings of the elements: at each level choose any unused element. Two implementations: a used[] boolean array (clear, general), or in-place swapping (swap(a[level], a[i]), recurse, swap back — O(1) extra space, subtler).

Intuition: Order mattering kills the start-index trick — every level must consider all elements, filtered by "already on the path." The tree has n! leaves and only leaves are solutions. Duplicate inputs (47) need the elegant rule: sort, then if (used[i-1] == false && a[i] == a[i-1]) continue — "among equal values, use them left-to-right": if the earlier twin isn't currently used, picking the later one now would recreate a branch the earlier one already generated.

Approach:

void bt(vector<int>& a, vector<bool>& used, vector<int>& path, vector<vector<int>>& out) {
    if (path.size() == a.size()) { out.push_back(path); return; }
    for (int i = 0; i < (int)a.size(); ++i) {
        if (used[i]) continue;
        if (i > 0 && a[i] == a[i-1] && !used[i-1]) continue;   // 47: equal values left-to-right
        used[i] = true;  path.push_back(a[i]);
        bt(a, used, path, out);
        used[i] = false; path.pop_back();
    }
}

What it is: Partition a string by choosing where each segment ends: palindrome partitioning (every segment a palindrome), IP restoration (exactly 4 segments, each 0–255), word-break-II (every segment in a dictionary). The choice at each level = "how long is the next piece?"

Intuition: The decision tree's branching factor is the segment length, and the state is just the current position — which is why these compose beautifully with precomputation and memoization: 131 precomputes a palindrome table (O(1) validity checks); in 140 the positions repeat across branches → memoize position → sentence-list, the textbook backtracking→DP hybrid. This is the same "partition by the next piece" move as the DP file's segmentation pattern — DP counts feasibility, backtracking materializes the pieces.

Approach:

void bt(string& s, int pos, vector<string>& path, vector<vector<string>>& out) {
    if (pos == (int)s.size()) { out.push_back(path); return; }
    for (int len = 1; pos + len <= (int)s.size(); ++len) {
        if (!valid(s, pos, len)) continue;        // palindrome / 0-255 / dictionary check
        path.push_back(s.substr(pos, len));
        bt(s, pos + len, path, out);
        path.pop_back();
    }
}

What it is: DFS from a cell through neighbors to match a target (a word, a path, max gold collected), marking cells visited in place and restoring them on the way out — backtracking where the "path state" is written into the board itself.

Intuition: The board is the used[] array: overwrite the cell with a sentinel ('#') on entry, restore the letter on exit — O(1) space, and the choose/undo symmetry is literal. Word Search II (212) is the marquee composition: searching many words cell-by-cell repeats prefix work → put the dictionary in a trie and walk board and trie together, pruning the instant the current path isn't a prefix of anything.

Approach:

bool dfs(vector<vector<char>>& b, int i, int j, string& w, int k) {
    if (k == (int)w.size()) return true;
    if (i < 0 || i >= (int)b.size() || j < 0 || j >= (int)b[0].size() || b[i][j] != w[k])
        return false;                              // bounds + match check = the prune
    char c = b[i][j]; b[i][j] = '#';               // choose: mark visited
    bool found = dfs(b,i+1,j,w,k+1) || dfs(b,i-1,j,w,k+1)
              || dfs(b,i,j+1,w,k+1) || dfs(b,i,j-1,w,k+1);
    b[i][j] = c;                                   // unchoose: restore
    return found;
}

A B C E
S F C S
A D E E

What it is: Place items on a board subject to global constraints: N-Queens (no shared row/column/diagonal), Sudoku (row/column/box uniqueness). Recurse position by position; at each, try every value/placement that passes the constraints; a dead end → backtrack.

Intuition: The efficiency insight is O(1) constraint checking via incremental bookkeeping: don't re-scan the board — keep sets/flags updated as you place and remove. N-Queens' diagonals collapse to two indices: r + c (anti-diagonal) and r − c + n (main diagonal); a placement flips three booleans, a conflict check reads three. Placing row-by-row bakes the row constraint into the recursion structure itself — structure eliminates constraints before code checks them.

Approach (N-Queens core):

void place(int r, int n, vector<int>& colOf,
           vector<bool>& col, vector<bool>& d1, vector<bool>& d2, int& count) {
    if (r == n) { ++count; return; }               // or materialize the board here
    for (int c = 0; c < n; ++c) {
        if (col[c] || d1[r + c] || d2[r - c + n]) continue;
        col[c] = d1[r + c] = d2[r - c + n] = true;  colOf[r] = c;
        place(r + 1, n, colOf, col, d1, d2, count);
        col[c] = d1[r + c] = d2[r - c + n] = false;
    }
}

What it is: Build strings character by character where a running invariant limits each next character: valid parentheses (may add ( while any remain; may add ) only if open > close so far), phone-number letters (a pure cartesian product — each digit contributes its letter set).

Intuition: Generate-then-filter would enumerate 2²ⁿ strings; constrain-during-generation walks only the valid ones — the invariant (close ≤ open ≤ n) prunes at the decision point, so every leaf reached is a valid answer, zero waste. This "invariant carried in the parameters" is the trees file's top-down state, driving generation instead of evaluation. Output size for 22 is the Catalan number Cₙ — name it when asked for complexity.

Approach:

void gen(int open, int close, int n, string& cur, vector<string>& out) {
    if ((int)cur.size() == 2 * n) { out.push_back(cur); return; }
    if (open < n)     { cur.push_back('('); gen(open + 1, close, n, cur, out); cur.pop_back(); }
    if (close < open) { cur.push_back(')'); gen(open, close + 1, n, cur, out); cur.pop_back(); }
}

What it is: Split items into k groups meeting a per-group condition (equal sums, matchstick square sides, fair cookie loads): for each item choose which bucket it joins — or, the dual view, fill buckets one at a time to the target. The hardest mainstream backtracking family (NP-hard in general — say so).

Intuition: The pruning arsenal decides feasibility in practice, and reciting it is the interview: (1) sort descending — big items fail fast, shrinking the tree near the root; (2) skip equal buckets — placing item x into empty bucket 3 mirrors empty bucket 2: if (bucket[j] == bucket[j-1]) continue; (symmetry breaking); (3) fail-fast arithmetic — total % k ≠ 0 → false, any item > target → false; (4) if an item fails in an empty bucket, no later arrangement saves it → abort the branch. The bucket-by-bucket dual + memo on item-bitmask is the DP escalation for tight cases — name it.

Approach:

bool bt(vector<int>& a, int idx, vector<int>& bucket, int target) {
    if (idx == (int)a.size()) return true;         // all placed (sums pre-validated)
    for (int j = 0; j < (int)bucket.size(); ++j) {
        if (j > 0 && bucket[j] == bucket[j-1]) continue;   // symmetric buckets: try once
        if (bucket[j] + a[idx] > target) continue;
        bucket[j] += a[idx];
        if (bt(a, idx + 1, bucket, target)) return true;
        bucket[j] -= a[idx];
        if (bucket[j] == 0) break;                 // failed in an empty bucket → hopeless
    }
    return false;
}