backtracking_patterns.cpp

/*
Backtracking & Combinatorial Patterns
Mathematical Foundation: Exhaustive search with pruning
Time Complexity: O(b^d) where b=branching factor, d=depth
Space: O(d) for recursion stack
Applications: Generate all combinations, permutations, subsets
*/

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

// Generate All Subsets
// LeetCode: 78. Subsets
// https://leetcode.com/problems/subsets/
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> path;
    function<void(int)> dfs = [&](int i) {
        res.push_back(path);
        for (int j = i; j < nums.size(); j++) {
            path.push_back(nums[j]);
            dfs(j + 1);
            path.pop_back();
        }
    };
    dfs(0);
    return res;
}

// Generate All Permutations
// LeetCode: 46. Permutations
// https://leetcode.com/problems/permutations/
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    function<void()> dfs = [&]() {
        if (nums.size() == 1) { res.push_back(nums); return; }
        for (int i = 0; i < nums.size(); i++) {
            int x = nums[i];
            nums.erase(nums.begin() + i);
            dfs();
            nums.insert(nums.begin() + i, x);
        }
    };
    dfs();
    return res;
}

// Combination Sum
// LeetCode: 39. Combination Sum
// https://leetcode.com/problems/combination-sum/
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> res;
    vector<int> path;
    function<void(int, int)> dfs = [&](int i, int sum) {
        if (sum == target) { res.push_back(path); return; }
        if (i >= candidates.size() || sum > target) return;
        path.push_back(candidates[i]);
        dfs(i, sum + candidates[i]);
        path.pop_back();
        dfs(i + 1, sum);
    };
    dfs(0, 0);
    return res;
}

// N-Queens
// LeetCode: 51. N-Queens
// https://leetcode.com/problems/n-queens/
vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<string> board(n, string(n, '.'));
    vector<bool> col(n), diag1(2*n), diag2(2*n);
    
    function<void(int)> dfs = [&](int r) {
        if (r == n) { res.push_back(board); return; }
        for (int c = 0; c < n; c++) {
            if (col[c] || diag1[r+c] || diag2[r-c+n]) continue;
            board[r][c] = 'Q';
            col[c] = diag1[r+c] = diag2[r-c+n] = true;
            dfs(r + 1);
            board[r][c] = '.';
            col[c] = diag1[r+c] = diag2[r-c+n] = false;
        }
    };
    dfs(0);
    return res;
}

// Generate Parentheses
// LeetCode: 22. Generate Parentheses
// https://leetcode.com/problems/generate-parentheses/
vector<string> generateParenthesis(int n) {
    vector<string> res;
    function<void(string, int, int)> dfs = [&](string s, int open, int close) {
        if (s.size() == 2 * n) { res.push_back(s); return; }
        if (open < n) dfs(s + "(", open + 1, close);
        if (close < open) dfs(s + ")", open, close + 1);
    };
    dfs("", 0, 0);
    return res;
}

// Word Search
// LeetCode: 79. Word Search
// https://leetcode.com/problems/word-search/
bool exist(vector<vector<char>>& board, string word) {
    int m = board.size(), n = board[0].size();
    function<bool(int, int, int)> dfs = [&](int r, int c, int i) -> bool {
        if (i == word.size()) return true;
        if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word[i]) return false;
        char tmp = board[r][c];
        board[r][c] = '#';
        bool found = dfs(r+1,c,i+1) || dfs(r-1,c,i+1) || dfs(r,c+1,i+1) || dfs(r,c-1,i+1);
        board[r][c] = tmp;
        return found;
    };
    
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
}

// Palindrome Partitioning
// LeetCode: 131. Palindrome Partitioning
// https://leetcode.com/problems/palindrome-partitioning/
vector<vector<string>> partition(string s) {
    vector<vector<string>> res;
    vector<string> path;
    
    auto isPalindrome = [](const string& str, int l, int r) {
        while (l < r) if (str[l++] != str[r--]) return false;
        return true;
    };
    
    function<void(int)> dfs = [&](int start) {
        if (start == s.size()) { res.push_back(path); return; }
        for (int end = start; end < s.size(); end++) {
            if (isPalindrome(s, start, end)) {
                path.push_back(s.substr(start, end - start + 1));
                dfs(end + 1);
                path.pop_back();
            }
        }
    };
    dfs(0);
    return res;
}

// Letter Combinations of Phone Number
// LeetCode: 17. Letter Combinations of a Phone Number
// https://leetcode.com/problems/letter-combinations-of-a-phone-number/
vector<string> letterCombinations(string digits) {
    if (digits.empty()) return {};
    vector<string> mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> res;
    string path;
    
    function<void(int)> dfs = [&](int i) {
        if (i == digits.size()) { res.push_back(path); return; }
        for (char c : mapping[digits[i] - '0']) {
            path.push_back(c);
            dfs(i + 1);
            path.pop_back();
        }
    };
    dfs(0);
    return res;
}

// Sudoku Solver
// LeetCode: 37. Sudoku Solver
// https://leetcode.com/problems/sudoku-solver/
void solveSudoku(vector<vector<char>>& board) {
    auto isValid = [&](int r, int c, char num) {
        for (int i = 0; i < 9; i++) {
            if (board[r][i] == num || board[i][c] == num || 
                board[3*(r/3)+i/3][3*(c/3)+i%3] == num) return false;
        }
        return true;
    };
    
    function<bool()> solve = [&]() -> bool {
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') {
                    for (char num = '1'; num <= '9'; num++) {
                        if (isValid(r, c, num)) {
                            board[r][c] = num;
                            if (solve()) return true;
                            board[r][c] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    };
    solve();
}

// Restore IP Addresses
// LeetCode: 93. Restore IP Addresses
// https://leetcode.com/problems/restore-ip-addresses/
vector<string> restoreIpAddresses(string s) {
    vector<string> res;
    vector<string> path;
    
    auto isValid = [](const string& segment) {
        return segment.size() <= 3 && stoi(segment) <= 255 && 
               (segment[0] != '0' || segment.size() == 1);
    };
    
    function<void(int)> dfs = [&](int start) {
        if (path.size() == 4) {
            if (start == s.size()) {
                res.push_back(path[0] + "." + path[1] + "." + path[2] + "." + path[3]);
            }
            return;
        }
        for (int len = 1; len <= 3 && start + len <= s.size(); len++) {
            string segment = s.substr(start, len);
            if (isValid(segment)) {
                path.push_back(segment);
                dfs(start + len);
                path.pop_back();
            }
        }
    };
    dfs(0);
    return res;
}