Recursion & Backtracking

// Factorial: n! = n × (n-1) × ... × 1
int factorial(int n) {
    if (n <= 1) return 1;           // Base case: 0! = 1! = 1
    return n * factorial(n - 1);   // Recursive case: n × (n-1)!
}
 
// Fibonacci: fib(n) = fib(n-1) + fib(n-2)
int fib(int n) {
    if (n <= 1) return n;           // Base cases: fib(0)=0, fib(1)=1
    return fib(n-1) + fib(n-2);    // Recursive case
}

// "Given that reverseList(head->next) correctly reverses the rest,
//  how do I make the full list reversed?"
ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;    // Base case
    ListNode* reversed = reverseList(head->next);  // Trust this works
    head->next->next = head;  // Now make current head the new tail
    head->next = nullptr;
    return reversed;
}

// ❌ Missing base case → infinite recursion → stack overflow
int f(int n) { return n * f(n-1); }   // Never stops!
 
// ❌ Base case that doesn't reduce correctly
int f(int n) {
    if (n == 0) return 0;
    return f(n);   // Not n-1, doesn't converge!
}
 
// ❌ Off-by-one in base case
int f(int n) {
    if (n == 1) return 1;   // What about n=0? Causes issues for some inputs
    return n * f(n-1);
}
 
// ✅ Correct
int f(int n) {
    if (n <= 0) return 1;   // Safe base case covers 0 and negative
    return n * f(n-1);
}

// Generic memoization with unordered_map
unordered_map<int, int> memo;
 
int fib(int n) {
    if (n <= 1) return n;
    if (memo.count(n)) return memo[n];   // Cache hit → return immediately
    memo[n] = fib(n-1) + fib(n-2);      // Cache miss → compute and store
    return memo[n];
}
// Time: O(n) — each unique n computed once
// Space: O(n) — memo map + O(n) call stack
 
// With vector (faster for bounded n):
vector<int> dp(n+1, -1);
int fib(int n) {
    if (n <= 1) return n;
    if (dp[n] != -1) return dp[n];
    return dp[n] = fib(n-1) + fib(n-2);
}

// Longest Common Subsequence with memoization
string s, t;
vector<vector<int>> memo;
 
int lcs(int i, int j) {
    if (i < 0 || j < 0) return 0;
    if (memo[i][j] != -1) return memo[i][j];
 
    if (s[i] == t[j])
        return memo[i][j] = 1 + lcs(i-1, j-1);
    return memo[i][j] = max(lcs(i-1, j), lcs(i, j-1));
}
 
// Call: memo.assign(n, vector<int>(m, -1)); lcs(n-1, m-1);

void backtrack(
    int       start,      // Current position in decision tree
    vector<T>& current,   // Current partial solution (state)
    vector<vector<T>>& result,  // All complete solutions found
    /* problem-specific parameters */
) {
    // 1. BASE CASE: Is the current state a complete solution?
    if (isComplete(current)) {
        result.push_back(current);
        return;
    }
 
    // 2. EXPLORE: Try each possible choice from current state
    for (int i = start; i < choices.size(); i++) {
        // 3. PRUNE: Skip invalid choices early
        if (!isValid(i, current)) continue;
 
        // 4. CHOOSE
        current.push_back(choices[i]);
 
        // 5. EXPLORE (recurse with choice made)
        backtrack(i + 1, current, result, /* ... */);
        //      or i (if repetition allowed)
 
        // 6. UNCHOOSE (undo to try next choice)
        current.pop_back();
    }
}

void backtrack(vector<int>& nums, int start, vector<int>& curr,
               vector<vector<int>>& result) {
    result.push_back(curr);   // Every partial state IS a valid subset
 
    for (int i = start; i < (int)nums.size(); i++) {
        curr.push_back(nums[i]);     // Choose: include nums[i]
        backtrack(nums, i+1, curr, result);  // Explore
        curr.pop_back();             // Unchoose
    }
}
 
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> curr;
    backtrack(nums, 0, curr, result);
    return result;
}
// Time: O(2^n × n) — 2^n subsets, each copied in O(n)
// Space: O(n) — recursion depth + curr array

vector<vector<int>> subsets(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> result;
 
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> subset;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) subset.push_back(nums[i]);
        }
        result.push_back(subset);
    }
    return result;
}
// Time: O(2^n × n), Space: O(n) extra
// Best for n ≤ 20 (fits in int) or n ≤ 30 (fits in long long)

void backtrack(vector<int>& nums, int start, vector<int>& curr,
               vector<vector<int>>& result) {
    result.push_back(curr);
 
    for (int i = start; i < (int)nums.size(); i++) {
        // Skip duplicates at the SAME recursion level
        if (i > start && nums[i] == nums[i-1]) continue;
 
        curr.push_back(nums[i]);
        backtrack(nums, i+1, curr, result);
        curr.pop_back();
    }
}
 
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end());   // Sort first!
    vector<vector<int>> result;
    vector<int> curr;
    backtrack(nums, 0, curr, result);
    return result;
}
/*
  Why i > start (not i > 0)?
  nums = [1, 2, 2], sorted
  At level 0 (start=0): i=1 (pick first 2), i=2 skip (same as nums[1]=2)
    → [2] is generated once
  At level 1 (start=1, already picked first 2): i=2 (pick second 2)
    → [2,2] is generated (fine, different subset)
  If we used i > 0: we'd skip the second 2 even when starting fresh
*/

void backtrack(vector<int>& nums, vector<bool>& used,
               vector<int>& curr, vector<vector<int>>& result) {
    if (curr.size() == nums.size()) {
        result.push_back(curr);
        return;
    }
    for (int i = 0; i < (int)nums.size(); i++) {
        if (used[i]) continue;        // Skip already-used elements
        used[i] = true;               // Choose
        curr.push_back(nums[i]);
        backtrack(nums, used, curr, result);  // Explore
        curr.pop_back();              // Unchoose
        used[i] = false;
    }
}
 
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    vector<bool> used(nums.size(), false);
    vector<int> curr;
    backtrack(nums, used, curr, result);
    return result;
}
// Time: O(n! × n), Space: O(n)

void backtrack(vector<int>& nums, vector<bool>& used,
               vector<int>& curr, vector<vector<int>>& result) {
    if (curr.size() == nums.size()) { result.push_back(curr); return; }
 
    for (int i = 0; i < (int)nums.size(); i++) {
        if (used[i]) continue;
        // Skip: same value AND previous same value was NOT used
        // (if prev was used, current would be in a different position → different perm)
        if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
 
        used[i] = true;
        curr.push_back(nums[i]);
        backtrack(nums, used, curr, result);
        curr.pop_back();
        used[i] = false;
    }
}
 
vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;
    vector<bool> used(nums.size(), false);
    vector<int> curr;
    backtrack(nums, used, curr, result);
    return result;
}
/*
  Why !used[i-1] (not used[i-1])?
  nums = [1, 1, 2]
  When generating [1(a), 1(b), 2]:
    i=0 used → i=1 both 1s valid if we don't skip
  When generating [1(b), 1(a), 2]:
    i=0 (first 1) skip because nums[0]==nums[-1]? No, i=0 has no prev.
  The condition !used[i-1] means:
    "If the previous same element was NOT chosen before the current element,
     we'd be generating the same permutation (just with a different choice order)."
*/

void backtrack(vector<int>& candidates, int target, int start,
               vector<int>& curr, vector<vector<int>>& result) {
    if (target == 0) { result.push_back(curr); return; }
    if (target < 0) return;   // Prune: exceeded target
 
    for (int i = start; i < (int)candidates.size(); i++) {
        curr.push_back(candidates[i]);
        backtrack(candidates, target - candidates[i], i, curr, result);
        //                                              ↑ i not i+1 (allow reuse)
        curr.pop_back();
    }
}
 
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> result;
    vector<int> curr;
    backtrack(candidates, target, 0, curr, result);
    return result;
}
// Time: O(N^(T/M)) where N=candidates, T=target, M=minimum candidate

void backtrack(vector<int>& candidates, int target, int start,
               vector<int>& curr, vector<vector<int>>& result) {
    if (target == 0) { result.push_back(curr); return; }
 
    for (int i = start; i < (int)candidates.size(); i++) {
        if (candidates[i] > target) break;  // Pruned: sorted, rest are too large
        if (i > start && candidates[i] == candidates[i-1]) continue;  // Skip duplicates
 
        curr.push_back(candidates[i]);
        backtrack(candidates, target - candidates[i], i+1, curr, result);
        //                                               ↑ i+1 (no reuse)
        curr.pop_back();
    }
}

void backtrack(int open, int close, int n, string& curr, vector<string>& result) {
    if (curr.size() == 2*n) { result.push_back(curr); return; }
 
    if (open < n) {
        curr += '(';
        backtrack(open+1, close, n, curr, result);
        curr.pop_back();
    }
    if (close < open) {   // Can only close if we have unclosed opens
        curr += ')';
        backtrack(open, close+1, n, curr, result);
        curr.pop_back();
    }
}
 
vector<string> generateParenthesis(int n) {
    vector<string> result;
    string curr;
    backtrack(0, 0, n, curr, result);
    return result;
}
// Time: O(4^n / sqrt(n)) — Catalan number
// The pruning (close < open) eliminates all invalid states

class NQueens {
    int n;
    vector<bool> cols, diag1, diag2;  // Attack trackers
 
    void backtrack(int row, vector<string>& board, vector<vector<string>>& result) {
        if (row == n) {
            result.push_back(board);   // All rows placed → complete solution
            return;
        }
        for (int col = 0; col < n; col++) {
            // Check if this cell is under attack
            if (cols[col] || diag1[row-col+n] || diag2[row+col]) continue;
 
            // Place queen
            board[row][col] = 'Q';
            cols[col] = diag1[row-col+n] = diag2[row+col] = true;
 
            backtrack(row+1, board, result);
 
            // Remove queen
            board[row][col] = '.';
            cols[col] = diag1[row-col+n] = diag2[row+col] = false;
        }
    }
 
public:
    vector<vector<string>> solveNQueens(int n) {
        this->n = n;
        cols.assign(n, false);
        diag1.assign(2*n, false);   // row-col ranges from -(n-1) to n-1, offset by n
        diag2.assign(2*n, false);   // row+col ranges from 0 to 2(n-1)
 
        vector<vector<string>> result;
        vector<string> board(n, string(n, '.'));
        backtrack(0, board, result);
        return result;
    }
};
// Time: O(n!) — at most n! arrangements to check
// Space: O(n) — recursion depth n + O(n) for trackers

int totalNQueens(int n) {
    vector<bool> cols(n), diag1(2*n), diag2(2*n);
    int count = 0;
 
    function<void(int)> bt = [&](int row) {
        if (row == n) { count++; return; }
        for (int col = 0; col < n; col++) {
            if (cols[col] || diag1[row-col+n] || diag2[row+col]) continue;
            cols[col] = diag1[row-col+n] = diag2[row+col] = true;
            bt(row+1);
            cols[col] = diag1[row-col+n] = diag2[row+col] = false;
        }
    };
    bt(0);
    return count;
}

class SudokuSolver {
    bool rows[9][10]  = {};  // rows[r][d]: digit d used in row r
    bool cols[9][10]  = {};  // cols[c][d]: digit d used in col c
    bool boxes[9][10] = {};  // boxes[b][d]: digit d used in box b
 
    int boxIdx(int r, int c) { return (r/3)*3 + c/3; }
 
    bool solve(vector<vector<char>>& board) {
        // Find next empty cell
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] != '.') continue;
 
                // Try each digit 1-9
                for (int d = 1; d <= 9; d++) {
                    if (rows[r][d] || cols[c][d] || boxes[boxIdx(r,c)][d]) continue;
 
                    // Place digit
                    board[r][c] = '0' + d;
                    rows[r][d] = cols[c][d] = boxes[boxIdx(r,c)][d] = true;
 
                    if (solve(board)) return true;  // Solution found!
 
                    // Remove digit (backtrack)
                    board[r][c] = '.';
                    rows[r][d] = cols[c][d] = boxes[boxIdx(r,c)][d] = false;
                }
                return false;  // No valid digit → backtrack further
            }
        }
        return true;  // No empty cell found → board is complete
    }
 
public:
    void solveSudoku(vector<vector<char>>& board) {
        // Pre-fill constraints from given board
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') continue;
                int d = board[r][c] - '0';
                rows[r][d] = cols[c][d] = boxes[boxIdx(r,c)][d] = true;
            }
        }
        solve(board);
    }
};
// Time: O(9^m) where m = number of empty cells (≤ 81)
// In practice much faster due to heavy pruning from row/col/box constraints

bool wordSearch(vector<vector<char>>& board, string word) {
    int rows = board.size(), cols = board[0].size();
    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
 
    function<bool(int,int,int)> dfs = [&](int r, int c, int k) -> bool {
        if (k == (int)word.size()) return true;   // All characters matched
        if (r<0||r>=rows||c<0||c>=cols) return false;
        if (board[r][c] != word[k]) return false;
 
        char saved = board[r][c];
        board[r][c] = '#';   // Mark as visited (in-place)
 
        for (int d = 0; d < 4; d++) {
            if (dfs(r+dx[d], c+dy[d], k+1)) {
                board[r][c] = saved;  // Restore before returning
                return true;
            }
        }
        board[r][c] = saved;   // Restore (backtrack)
        return false;
    };
 
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (dfs(r, c, 0)) return true;
 
    return false;
}
// Time: O(rows×cols × 4 × 3^(L-1)) where L = word length
//   4 choices for first cell, 3 for each subsequent (can't go back)
// Space: O(L) — recursion depth

// In combination sum: if current element > remaining target, stop
for (int i = start; i < candidates.size(); i++) {
    if (candidates[i] > target) break;   // Sorted array → rest also exceed
    // ...
}

// At same recursion level, skip elements equal to the previous one
for (int i = start; i < nums.size(); i++) {
    if (i > start && nums[i] == nums[i-1]) continue;   // Skip duplicates
    // ...
}

// If not enough elements remain to complete the solution, prune
void backtrack(int start, int k, vector<int>& curr, ...) {
    // Need k-curr.size() more elements; only n-start elements remain
    if ((int)nums.size() - start < k - (int)curr.size()) return;  // Pruned!
    if (curr.size() == k) { result.push_back(curr); return; }
    // ...
}

// For palindrome partitioning: precompute which substrings are palindromes
// O(n²) precomputation → O(1) palindrome check during backtracking
vector<vector<bool>> isPalin;
void precompute(const string& s) {
    int n = s.size();
    isPalin.assign(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) isPalin[i][i] = true;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            isPalin[i][j] = (s[i] == s[j]) && (len == 2 || isPalin[i+1][j-1]);
        }
    }
}

// For TSP / assignment problems: if current partial cost > best complete solution, prune
if (currentCost + lowerBoundEstimate >= bestCost) return;  // Can't improve → prune

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> curr;
    function<void(int)> bt = [&](int start) {
        result.push_back(curr);
        for (int i = start; i < (int)nums.size(); i++) {
            curr.push_back(nums[i]);
            bt(i+1);
            curr.pop_back();
        }
    };
    bt(0);
    return result;
}
// Time: O(2^n × n), Space: O(n)

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;
    vector<int> curr;
    function<void(int)> bt = [&](int start) {
        result.push_back(curr);
        for (int i = start; i < (int)nums.size(); i++) {
            if (i > start && nums[i] == nums[i-1]) continue;
            curr.push_back(nums[i]); bt(i+1); curr.pop_back();
        }
    };
    bt(0);
    return result;
}
// Time: O(2^n × n), Space: O(n)

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    vector<bool> used(nums.size(), false);
    vector<int> curr;
    function<void()> bt = [&]() {
        if (curr.size() == nums.size()) { result.push_back(curr); return; }
        for (int i = 0; i < (int)nums.size(); i++) {
            if (used[i]) continue;
            used[i] = true; curr.push_back(nums[i]);
            bt();
            used[i] = false; curr.pop_back();
        }
    };
    bt();
    return result;
}
// Time: O(n! × n), Space: O(n)

vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;
    vector<bool> used(nums.size(), false);
    vector<int> curr;
    function<void()> bt = [&]() {
        if (curr.size() == nums.size()) { result.push_back(curr); 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;
            used[i] = true; curr.push_back(nums[i]);
            bt();
            used[i] = false; curr.pop_back();
        }
    };
    bt();
    return result;
}
// Time: O(n! × n), Space: O(n)

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> result;
    vector<int> curr;
    function<void(int,int)> bt = [&](int start, int rem) {
        if (rem == 0) { result.push_back(curr); return; }
        for (int i = start; i < (int)candidates.size(); i++) {
            if (candidates[i] > rem) break;
            curr.push_back(candidates[i]);
            bt(i, rem - candidates[i]);   // i (not i+1): allow reuse
            curr.pop_back();
        }
    };
    bt(0, target);
    return result;
}
// Time: O(N^(T/M)) roughly, Space: O(T/M) depth

vector<string> generateParenthesis(int n) {
    vector<string> result;
    string curr;
    function<void(int,int)> bt = [&](int open, int close) {
        if ((int)curr.size() == 2*n) { result.push_back(curr); return; }
        if (open < n)     { curr+='('; bt(open+1, close); curr.pop_back(); }
        if (close < open) { curr+=')'; bt(open, close+1); curr.pop_back(); }
    };
    bt(0, 0);
    return result;
}
// Time: O(4^n / sqrt(n)) — Catalan number, Space: O(n)

vector<string> letterCombinations(string digits) {
    if (digits.empty()) return {};
    vector<string> phoneMap = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> result;
    string curr;
    function<void(int)> bt = [&](int idx) {
        if (idx == (int)digits.size()) { result.push_back(curr); return; }
        for (char c : phoneMap[digits[idx]-'0']) {
            curr += c; bt(idx+1); curr.pop_back();
        }
    };
    bt(0);
    return result;
}
// Time: O(4^n × n) where n = digits.length, Space: O(n)

bool exist(vector<vector<char>>& board, string word) {
    int R=board.size(), C=board[0].size();
    int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
    function<bool(int,int,int)> dfs=[&](int r,int c,int k)->bool {
        if(k==(int)word.size()) return true;
        if(r<0||r>=R||c<0||c>=C||board[r][c]!=word[k]) return false;
        char sv=board[r][c]; board[r][c]='#';
        for(int d=0;d<4;d++) if(dfs(r+dx[d],c+dy[d],k+1)){board[r][c]=sv;return true;}
        board[r][c]=sv;
        return false;
    };
    for(int r=0;r<R;r++) for(int c=0;c<C;c++) if(dfs(r,c,0)) return true;
    return false;
}
// Time: O(R×C×3^L), Space: O(L) where L=word length

vector<vector<string>> partition(string s) {
    int n = s.size();
    // Precompute palindrome table
    vector<vector<bool>> isPalin(n, vector<bool>(n, false));
    for (int i = n-1; i >= 0; i--)
        for (int j = i; j < n; j++)
            isPalin[i][j] = (s[i]==s[j]) && (j-i<2 || isPalin[i+1][j-1]);
 
    vector<vector<string>> result;
    vector<string> curr;
    function<void(int)> bt = [&](int start) {
        if (start == n) { result.push_back(curr); return; }
        for (int end = start; end < n; end++) {
            if (!isPalin[start][end]) continue;
            curr.push_back(s.substr(start, end-start+1));
            bt(end+1);
            curr.pop_back();
        }
    };
    bt(0);
    return result;
}
// Time: O(2^n × n), Space: O(n²) for palindrome table

vector<vector<string>> solveNQueens(int n) {
    vector<bool> cols(n), d1(2*n), d2(2*n);
    vector<vector<string>> result;
    vector<string> board(n, string(n,'.'));
 
    function<void(int)> bt = [&](int row) {
        if (row == n) { result.push_back(board); return; }
        for (int col = 0; col < n; col++) {
            if (cols[col]||d1[row-col+n]||d2[row+col]) continue;
            board[row][col]='Q';
            cols[col]=d1[row-col+n]=d2[row+col]=true;
            bt(row+1);
            board[row][col]='.';
            cols[col]=d1[row-col+n]=d2[row+col]=false;
        }
    };
    bt(0);
    return result;
}
// Time: O(n!), Space: O(n)

void solveSudoku(vector<vector<char>>& board) {
    bool rows[9][10]={}, cols[9][10]={}, boxes[9][10]={};
    auto box=[](int r,int c){ return (r/3)*3+c/3; };
 
    for(int r=0;r<9;r++) for(int c=0;c<9;c++) if(board[r][c]!='.') {
        int d=board[r][c]-'0';
        rows[r][d]=cols[c][d]=boxes[box(r,c)][d]=true;
    }
 
    function<bool()> solve=[&]()->bool {
        for(int r=0;r<9;r++) for(int c=0;c<9;c++) {
            if(board[r][c]!='.') continue;
            for(int d=1;d<=9;d++) {
                if(rows[r][d]||cols[c][d]||boxes[box(r,c)][d]) continue;
                board[r][c]='0'+d;
                rows[r][d]=cols[c][d]=boxes[box(r,c)][d]=true;
                if(solve()) return true;
                board[r][c]='.';
                rows[r][d]=cols[c][d]=boxes[box(r,c)][d]=false;
            }
            return false;
        }
        return true;
    };
    solve();
}
// Time: O(9^m) worst, fast in practice due to constraints

vector<vector<int>> combinationSum3(int k, int n) {
    vector<vector<int>> result;
    vector<int> curr;
    function<void(int,int)> bt = [&](int start, int rem) {
        if (curr.size()==(size_t)k && rem==0) { result.push_back(curr); return; }
        if ((int)curr.size()==k || rem<=0) return;
        for (int i=start; i<=9; i++) {
            if (i > rem) break;   // Prune: rest also too large
            curr.push_back(i);
            bt(i+1, rem-i);
            curr.pop_back();
        }
    };
    bt(1, n);
    return result;
}
// Time: O(C(9,k) × k), Space: O(k)