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

⭐️个人主页：@小羊 ⭐️所属专栏：LeetCode 热题 100 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

---

全排列

• 全排列

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;} 
};

---

N 皇后

• N 皇后

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] = '.';}}}
};

---

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~