Backtracking

// Universal Backtracking Template
void backtrack(State& state, vector<Result>& results) {
    // Base case: complete solution found
    if (isComplete(state)) {
        results.push_back(buildResult(state));
        return;
    }
    
    // Try every candidate for the next choice
    for (auto& candidate : getCandidates(state)) {
        if (!isValid(state, candidate)) continue; // prune invalid
        
        makeChoice(state, candidate);             // CHOOSE
        backtrack(state, results);                // EXPLORE
        undoChoice(state, candidate);             // UN-CHOOSE
    }
}

// LeetCode 78 — Subsets — O(2^n * n) Time, O(n) Space
class Solution {
    void bt(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
        res.push_back(path); // every node is a valid subset
        
        for (int i = start; i < (int)nums.size(); i++) {
            path.push_back(nums[i]);       // CHOOSE
            bt(nums, i+1, path, res);      // EXPLORE (i+1: no reuse)
            path.pop_back();               // UN-CHOOSE
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        bt(nums, 0, path, res);
        return res;
    }
};

// Subsets II — with duplicates (LC 90)
// Sort first, then skip nums[i] == nums[i-1] at the same recursion level.
void btII(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
    res.push_back(path);
    for (int i = start; i < (int)nums.size(); i++) {
        if (i > start && nums[i] == nums[i-1]) continue; // skip duplicate
        path.push_back(nums[i]);
        btII(nums, i+1, path, res);
        path.pop_back();
    }
}

// LeetCode 46 — Permutations (no duplicates) — O(n! * n) Time, O(n) Space
class Solution {
    void bt(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {
        if ((int)path.size() == (int)nums.size()) {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < (int)nums.size(); i++) {
            if (used[i]) continue; // already in path
            used[i] = true;        // CHOOSE
            path.push_back(nums[i]);
            
            bt(nums, used, path, res); // EXPLORE
            
            path.pop_back();       // UN-CHOOSE
            used[i] = false;
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<bool> used(nums.size(), false);
        vector<int> path;
        bt(nums, used, path, res);
        return res;
    }
};

// Permutations II — with duplicates (LC 47)
// Sort first. Skip nums[i]==nums[i-1] when nums[i-1] is NOT used.
// (This means we only take the first copy of a duplicate at each level.)
void btII(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {
    if ((int)path.size() == (int)nums.size()) { res.push_back(path); return; }
    for (int i = 0; i < (int)nums.size(); i++) {
        if (used[i]) continue;
        if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue; // prune dup
        used[i] = true;
        path.push_back(nums[i]);
        btII(nums, used, path, res);
        path.pop_back();
        used[i] = false;
    }
}

// LeetCode 77 — Combinations: choose k numbers from [1..n] — O(C(n,k) * k)
class Solution {
    void bt(int n, int k, int start, vector<int>& path, vector<vector<int>>& res) {
        if ((int)path.size() == k) {
            res.push_back(path);
            return;
        }
        // Pruning: need k-path.size() more elements, at most n-i+1 remain
        for (int i = start; i <= n - (k - (int)path.size()) + 1; i++) {
            path.push_back(i);       // CHOOSE
            bt(n, k, i+1, path, res); // EXPLORE
            path.pop_back();         // UN-CHOOSE
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> path;
        bt(n, k, 1, path, res);
        return res;
    }
};

// LeetCode 39 — Combination Sum — Time: O(N^(T/M)) N=candidates, T=target, M=min
class Solution {
    void bt(vector<int>& cands, int start, int remain, vector<int>& path, vector<vector<int>>& res) {
        if (remain == 0) { res.push_back(path); return; }
        
        for (int i = start; i < (int)cands.size(); i++) {
            if (cands[i] > remain) break; // sorted: all further are larger, PRUNE
            
            path.push_back(cands[i]);
            bt(cands, i, remain - cands[i], path, res); // i (not i+1): reuse ok
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end()); // sort to enable pruning
        vector<vector<int>> res;
        vector<int> path;
        bt(candidates, 0, target, path, res);
        return res;
    }
};

// LeetCode 51 — N-Queens — O(N!) Time, O(N) Space
// Place N queens on N×N board so none attack each other.
class Solution {
    vector<vector<string>> res;
    vector<bool> col, diag1, diag2; // col, '/' diagonal, '\' diagonal
    
    void bt(int row, int n, vector<string>& board) {
        if (row == n) {
            res.push_back(board);
            return;
        }
        for (int c = 0; c < n; c++) {
            // Prune: column or either diagonal is occupied
            if (col[c] || diag1[row-c+n-1] || diag2[row+c]) continue;
            
            board[row][c] = 'Q';       // CHOOSE
            col[c] = diag1[row-c+n-1] = diag2[row+c] = true;
            
            bt(row+1, n, board);       // EXPLORE
            
            board[row][c] = '.';       // UN-CHOOSE
            col[c] = diag1[row-c+n-1] = diag2[row+c] = false;
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        col.assign(n,false);
        diag1.assign(2*n-1,false); // '/' diagonals: indexed by row-col+n-1
        diag2.assign(2*n-1,false); // '\' diagonals: indexed by row+col
        vector<string> board(n, string(n,'.'));
        bt(0, n, board);
        return res;
    }
};

// LeetCode 79 — Word Search — O(M*N * 4^L)
class Solution {
    bool bt(vector<vector<char>>& g, string& w, int idx, int r, int c) {
        if (idx == (int)w.size()) return true; // all chars matched
        if (r<0||r>=(int)g.size()||c<0||c>=(int)g[0].size()) return false;
        if (g[r][c] != w[idx]) return false;   // mismatch: prune
        
        char tmp = g[r][c];
        g[r][c] = '#'; // CHOOSE: mark visited
        
        bool found = bt(g,w,idx+1,r+1,c) || bt(g,w,idx+1,r-1,c) || 
                     bt(g,w,idx+1,r,c+1) || bt(g,w,idx+1,r,c-1);
                     
        g[r][c] = tmp; // UN-CHOOSE: restore cell
        return found;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int r=0; r<(int)board.size(); r++)
            for (int c=0; c<(int)board[0].size(); c++)
                if (bt(board, word, 0, r, c)) return true;
        return false;
    }
};

// LeetCode 22 — Generate Parentheses — O(4^n / sqrt(n)) Catalan number
class Solution {
    void bt(int n, int open, int close, string& curr, vector<string>& res) {
        if ((int)curr.size() == 2*n) { res.push_back(curr); return; }
        
        if (open < n) { // can add '('
            curr.push_back('(');
            bt(n, open+1, close, curr, res);
            curr.pop_back();
        }
        if (close < open) { // can add ')' only if open > close
            curr.push_back(')');
            bt(n, open, close+1, curr, res);
            curr.pop_back();
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res; string curr;
        bt(n, 0, 0, curr, res);
        return res;
    }
};

// LeetCode 131 — Palindrome Partitioning — O(2^n * n) Time, O(n) Space
class Solution {
    bool isPalin(string& s, int l, int r) {
        while (l < r) if (s[l++] != s[r--]) return false;
        return true;
    }
    void bt(string& s, int start, vector<string>& path, vector<vector<string>>& res) {
        if (start == (int)s.size()) { res.push_back(path); return; }
        
        for (int end = start; end < (int)s.size(); end++) {
            if (!isPalin(s, start, end)) continue; // prune non-palindromes
            path.push_back(s.substr(start, end-start+1));
            bt(s, end+1, path, res);
            path.pop_back();
        }
    }
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res; vector<string> path;
        bt(s, 0, path, res);
        return res;
    }
};

// LeetCode 37 — Sudoku Solver — O(9^M) Time M=empty cells, O(M) Space
class Solution {
    bool isValid(vector<vector<char>>& b, int r, int c, char d) {
        for (int i=0;i<9;i++) {
            if (b[r][i]==d || b[i][c]==d) return false;
            if (b[3*(r/3)+i/3][3*(c/3)+i%3]==d) return false;
        }
        return true;
    }
    bool bt(vector<vector<char>>& b) {
        for (int r=0;r<9;r++) {
            for (int c=0;c<9;c++) {
                if (b[r][c] != '.') continue;
                for (char d='1'; d<='9'; d++) {
                    if (!isValid(b,r,c,d)) continue;
                    b[r][c] = d;
                    if (bt(b)) return true;
                    b[r][c] = '.';
                }
                return false; // no digit worked: backtrack
            }
        }
        return true; // all cells filled
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        bt(board);
    }
};