【LeetCode 热题 100】全排列 / 子集 / 组合总和 / 分割回文串 / N 皇后

class Solution {
    vector<vector<int>> res;
    vector<int> path;
    bool used[7] = {};
    int n;
public:
    vector<vector<int>> permute(vector<int>& nums) {
        n = nums.size();
        dfs(nums);
        return res;
    }
    void dfs(vector<int>& nums)
    {
        if (path.size() == n)
        {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < n; i++)
        {
            if (!used[i])
            {
                used[i] = true;
                path.push_back(nums[i]);
                dfs(nums);
                used[i] = false;
                path.pop_back();
            }
        }
    }
};

class Solution {
    vector<vector<int>> res;
    vector<int> path;
    bool used[11] = {};
    int n;
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        n = nums.size();
        dfs(nums, 0);
        return res;
    }
    void dfs(vector<int>& nums, int pos)
    {
        res.push_back(path);
        for (int i = pos; i < n; i++)
        {
            if (!used[i])
            {
                used[i] = true;
                path.push_back(nums[i]);
                dfs(nums, i + 1);
                used[i] = false;
                path.pop_back();
            }
        }
    }
};

class Solution {
    string hash[10] = {"", "", "abc", "def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> res;
    string path;
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return res;
        dfs(digits, 0);
        return res;
    }
    void dfs(string& digits, int pos)
    {
        if (pos == digits.size())
        {
            res.push_back(path);
            return;
        }
        for (auto e : hash[digits[pos] - '0'])
        {
            path += e;
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
};

class Solution {
    vector<vector<int>> res;
    vector<int> path;
    int t;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        t = target;
        dfs(candidates, 0, 0);
        return res;
    }
    void dfs(vector<int>& candidates, int pos, int sum)
    {
        if (sum == t)
        {
            res.push_back(path);
            return;
        }
        else if (sum > t) return;
        for (int i = pos; i < candidates.size(); i++)
        {
            path.push_back(candidates[i]);
            dfs(candidates, i, sum + candidates[i]);
            path.pop_back();
        }
    }
};

class Solution {
    vector<string> res;
    string path;
    int left, right, m;
public:
    vector<string> generateParenthesis(int n) {
        m = n;
        dfs();
        return res;
    }
    void dfs()
    {
        if (right == m)
        {
            res.push_back(path);
            return;
        }
        if (left < m)
        {
            path += "(";
            left++;
            dfs();
            path.pop_back();
            left--;
        }
        if (right < left)
        {
            path += ")";
            right++;
            dfs();
            path.pop_back();
            right--;
        }
    }
};

class Solution {
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    bool used[7][7] = {};
    int m, n;
public:
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (board[i][j] == word[0])
                {
                    if (dfs(board, word, i, j, 1)) return true;
                }
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int pos)
    {
        if (pos == word.size()) return true;
        used[i][j] = true;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !used[x][y] && board[x][y] == word[pos])
            {
                if (dfs(board, word, x, y, pos + 1)) return true;
            }
        }
        used[i][j] = false;
        return false;
    }
};

class Solution {
    vector<vector<string>> res;
    vector<string> path;
public:
    vector<vector<string>> partition(string s) {
        dfs(s, 0);
        return res;
    }
    void dfs(string& s, int pos)
    {
        if (pos == s.size())
        {
            res.push_back(path);
            return;
        }
        for (int i = pos; i < s.size(); i++)
        {
            if (check(s, pos, i))
            {
                path.push_back(s.substr(pos, i - pos + 1));
                dfs(s, i + 1);
                path.pop_back();
            }
        }
    }
    bool check(string& s, int l, int r)
    {
        while (l < r && s[l] == s[r])
        {
            l++, r--;
        }
        return l >= r;
    } 
};

class Solution {
    vector<vector<string>> res;
    vector<string> path;
    bool checkcol[10], checkdig1[20], checkdig2[20];
    int m;
public:
    vector<vector<string>> solveNQueens(int n) {
        m = n;
        path.resize(n);
        for (int i = 0; i < n; i++) path[i].append(n, '.');
        dfs(0);
        return res;
    }
    void dfs(int row)
    {
        if (row == m)
        {
            res.push_back(path);
            return;
        }
        for (int col = 0; col < m; col++) // 尝试在当前行放Q
        {
            if (!checkcol[col] && !checkdig1[col - row + m] && !checkdig2[col + row])
            {
                checkcol[col] = checkdig1[col - row + m] = checkdig2[col + row] = true;
                path[row][col] = 'Q';
                dfs(row + 1);
                checkcol[col] = checkdig1[col - row + m] = checkdig2[col + row] = false;
                path[row][col] = '.';
            }
        }
    }
};