Backtracking Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

// Subsets: every call is one subset; the loop picks the NEXT element to add, always to the right.
// Sort first and skip equal neighbours at the same depth to avoid duplicate subsets (Subsets II).
void build(const vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& out) {
    out.push_back(path);                                 // every node of the tree is an answer
    for (int i = start; i < (int)nums.size(); i++) {
        if (i > start && nums[i] == nums[i - 1]) continue; // same value already tried at this depth
        path.push_back(nums[i]);                         // choose
        build(nums, i + 1, path, out);                   // explore: only elements to the right
        path.pop_back();                                 // un-choose
    }
}

vector<vector<int>> subsetsWithDup(vector<int> nums) {
    sort(nums.begin(), nums.end());                      // equal values side by side
    vector<vector<int>> out;
    vector<int> path;
    build(nums, 0, path, out);
    return out;
}

// Permutations: fill positions one by one with any element not used yet.
// With duplicates: sort, and use equal copies only in left-to-right order (skip if the left copy is unused).
void build(const vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& out) {
    if (path.size() == nums.size()) { out.push_back(path); return; }
    for (int i = 0; i < (int)nums.size(); i++) {         // any position: loop from 0, not from start
        if (used[i]) continue;
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // duplicate branch
        used[i] = true;  path.push_back(nums[i]);        // choose
        build(nums, used, path, out);                    // explore
        path.pop_back(); used[i] = false;                // un-choose
    }
}

vector<vector<int>> permuteUnique(vector<int> nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> out;
    vector<int> path;
    vector<bool> used(nums.size(), false);
    build(nums, used, path, out);
    return out;
}

// Choose K: pick items in increasing order (start index), so each group appears once.
// Prune when the numbers left can't fill the remaining slots.
void build(int n, int k, int start, vector<int>& path, vector<vector<int>>& out) {
    if ((int)path.size() == k) { out.push_back(path); return; }
    int need = k - path.size();
    for (int i = start; i <= n - need + 1; i++) {        // i > n-need+1 leaves too few numbers
        path.push_back(i);
        build(n, k, i + 1, path, out);                   // next pick must be larger
        path.pop_back();
    }
}

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> out;
    vector<int> path;
    build(n, k, 1, path, out);
    return out;
}

// Combination sum: target-driven. Sorted candidates let us stop as soon as one is too big.
//   reuse allowed (LC 39): recurse on i      no reuse (LC 40): recurse on i+1 and skip equal neighbours
void build(const vector<int>& c, int start, int remaining, bool reuse,
           vector<int>& path, vector<vector<int>>& out) {
    if (remaining == 0) { out.push_back(path); return; }
    for (int i = start; i < (int)c.size(); i++) {
        if (c[i] > remaining) break;                     // sorted: everything after is too big too
        if (!reuse && i > start && c[i] == c[i - 1]) continue;
        path.push_back(c[i]);
        build(c, reuse ? i : i + 1, remaining - c[i], reuse, path, out);
        path.pop_back();
    }
}

vector<vector<int>> combinationSum(vector<int> candidates, int target, bool reuse) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> out;
    vector<int> path;
    build(candidates, 0, target, reuse, path, out);
    return out;
}

// String partitioning: cut off a valid first piece s[start..end], recurse on the rest.
// Here the rule is "piece is a palindrome", answered in O(1) by a table built once in O(n^2).
void build(const string& s, int start, const vector<vector<bool>>& ok,
           vector<string>& pieces, vector<vector<string>>& out) {
    if (start == (int)s.size()) { out.push_back(pieces); return; } // the whole string is cut
    for (int end = start; end < (int)s.size(); end++) {
        if (!ok[start][end]) continue;                   // invalid piece: prune this branch
        pieces.push_back(s.substr(start, end - start + 1));
        build(s, end + 1, ok, pieces, out);
        pieces.pop_back();
    }
}

vector<vector<string>> partition(const string& s) {
    int n = s.size();
    vector<vector<bool>> ok(n, vector<bool>(n, false));  // ok[i][j]: s[i..j] is a palindrome
    for (int i = n - 1; i >= 0; i--)
        for (int j = i; j < n; j++)
            ok[i][j] = s[i] == s[j] && (j - i < 2 || ok[i + 1][j - 1]);
    vector<vector<string>> out;
    vector<string> pieces;
    build(s, 0, ok, pieces, out);
    return out;
}

// Constraint satisfaction: place one item per step (a queen per row), check the rules in O(1)
// with "taken" arrays, and undo all of them on the way back.
void place(int r, int n, vector<string>& board, vector<bool>& col, vector<bool>& diag,
           vector<bool>& anti, vector<vector<string>>& out) {
    if (r == n) { out.push_back(board); return; }        // every row has a queen
    for (int c = 0; c < n; c++) {
        if (col[c] || diag[r + c] || anti[r - c + n - 1]) continue; // attacked: prune
        board[r][c] = 'Q'; col[c] = diag[r + c] = anti[r - c + n - 1] = true;
        place(r + 1, n, board, col, diag, anti, out);
        board[r][c] = '.'; col[c] = diag[r + c] = anti[r - c + n - 1] = false;
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<string> board(n, string(n, '.'));
    vector<bool> col(n), diag(2 * n - 1), anti(2 * n - 1);
    vector<vector<string>> out;
    place(0, n, board, col, diag, anti, out);
    return out;
}

// Grid path: mark the cell on the way in, unmark on the way out,
// so other paths may still pass through it later (Word Search).
bool dfs(vector<vector<char>>& g, const string& word, int i, int r, int c) {
    if (i == (int)word.size()) return true;              // every letter matched
    if (r < 0 || c < 0 || r >= (int)g.size() || c >= (int)g[0].size() || g[r][c] != word[i])
        return false;                                    // off the grid, used, or wrong letter
    char saved = g[r][c];
    g[r][c] = '#';                                       // mark: in use on this path
    bool found = dfs(g, word, i + 1, r + 1, c) || dfs(g, word, i + 1, r - 1, c) ||
                 dfs(g, word, i + 1, r, c + 1) || dfs(g, word, i + 1, r, c - 1);
    g[r][c] = saved;                                     // unmark: free for other paths
    return found;
}

bool exist(vector<vector<char>>& board, const string& word) {
    for (int r = 0; r < (int)board.size(); r++)
        for (int c = 0; c < (int)board[0].size(); c++)
            if (dfs(board, word, 0, r, c)) return true;
    return false;
}