46. 全排列
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> ans;
vector<int> v;
vector<int> vis(n, 0);
auto dfs = [&](this auto&& dfs, int dep) -> void {
if (dep == n) {
ans.push_back(v);
return;
}
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
vis[i] = 1;
v.push_back(nums[i]);
dfs(dep + 1);
vis[i] = 0;
v.pop_back();
}
};
dfs(0);
return ans;
}
};78. 子集
class Solution {
public:
vector<vector<int>> subsets(vector<int>& a) {
int n = a.size();
vector<vector<int>> ans;
for (int i = 0; i < 1 << n; i++) {
vector<int> v;
for (int j = 0; j < n; j++) {
if (i >> j & 1) {
v.push_back(a[j]);
}
}
ans.push_back(v);
}
return ans;
}
};二进制枚举，1表示选，0表示不选
17. 电话号码的字母组合
class Solution {
public:
vector<string> letterCombinations(string str) {
if (str == "") return {};
vector<string> ans;
map<char, string> mp;
int n = str.size();
mp['2'] = "abc";
mp['3'] = "def";
mp['4'] = "ghi";
mp['5'] = "jkl";
mp['6'] = "mno";
mp['7'] = "pqrs";
mp['8'] = "tuv";
mp['9'] = "wxyz";
auto dfs = [&](this auto&& dfs, int dep, string s) -> void {
if (dep == n) {
ans.push_back(s);
return;
}
for (auto ch : mp[str[dep]]) {
dfs(dep + 1, s + ch);
}
};
dfs(0, "");
return ans;
}
};39. 组合总和
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& a, int x) {
int n = a.size();
vector<vector<vector<int>>> g(41);
g[0].push_back({});
for (int i = 0; i < n; i++) {
for (int j = a[i]; j <= x; j++) {
for (auto v : g[j - a[i]]) {
v.push_back(a[i]);
g[j].push_back(v);
}
}
}
return g[x];
}
};背包记录方案数
22. 括号生成
class Solution {
public:
vector<string> generateParenthesis(int n) {
auto check = [](string s) -> bool {
if (s.size() & 1) return false;
int cnt = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') cnt++;
else {
if (cnt <= 0) return false;
cnt--;
}
}
return cnt == 0;
};
vector<string> ans;
auto dfs = [&](this auto&& dfs, int dep, string s) -> void {
if (dep == 2 * n) {
if (check(s)) ans.push_back(s);
return;
}
dfs(dep + 1, s + '(');
dfs(dep + 1, s + ')');
};
dfs(0, "");
return ans;
}
};dfs暴搜
79. 单词搜索
class Solution {
public:
bool exist(vector<vector<char>>& a, string word) {
vector<int> dx = { 0, 1, 0, -1 };
vector<int> dy = { 1, 0, -1, 0 };
int n = a.size(), m = a[0].size();
set<char> s;
for (auto ch : word) s.insert(ch);
vector<vector<int>> vis(n, vector<int>(m, 0));
auto dfs = [&](this auto&& dfs, int x, int y, string str) -> bool {
if (str.size() == word.size()) {
for (int i = 0; i < str.size(); i++) {
if (str[i] != word[i]) return false;
}
return true;
}
for (int i = 0; i < 4; i++) {
int tx = x + dx[i], ty = y + dy[i];
if (tx < 0 || ty < 0 || tx >= n || ty >= m) continue;
if (vis[tx][ty]) continue;
if (!s.count(a[tx][ty])) continue;
string tmp = str;
tmp += a[tx][ty];
vis[tx][ty] = 1;
if (dfs(tx, ty, tmp)) return true;
vis[tx][ty] = 0;
}
return false;
};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (s.count(a[i][j]) == 0) continue;
if (a[i][j] != word[0]) continue;
string tmp = "";
tmp += a[i][j];
vis[i][j] = 1;
if (dfs(i, j, tmp)) return true;
vis[i][j] = 0;
}
}
return false;
}
};注意dfs里面是 if (dfs(tx, ty, tmp)) return true;
不能直接 return dfs(tx, ty, tmp)
此外字符串拼接用+=
131. 分割回文串
class Solution {
public:
vector<vector<string>> partition(string s) {
int n = s.size();
vector<vector<string>> ans;
auto check = [](string s) -> bool {
for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
if (s[i] != s[j]) return false;
}
return true;
};
for (int i = 0; i < 1 << n; i++) {
vector<string> v;
string str = "";
int ok = 1;
for (int j = 0; j < n; j++) {
str += s[j];
if (i >> j & 1) {
if (check(str)) v.push_back(str);
else ok = 0;
str = "";
}
}
if (str != "" && check(str)) v.push_back(str);
else ok = 0;
if (ok) ans.push_back(v);
}
return ans;
}
};二进制枚举状态，1表示分割，0表示不分割
51. N 皇后
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
if (n == 1) {
vector<string> v;
v.push_back("Q");
ans.push_back(v);
return ans;
}
vector<string> a;
string s = "";
for (int i = 0; i < n; i++) {
s += '.';
}
for (int i = 0; i < n; i++) {
a.push_back(s);
}
auto check = [&]() -> bool {
/*
check 斜线
*/
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j += n - 1)
{
for (int k = -1; k <= 1; k += 2) {
int cnt = 0;
int x = i, y = j;
while (x >= 0 && y >= 0 && x < n && y < n) {
cnt += a[x][y] == 'Q';
x++;
y += k;
}
if (cnt > 1) return false;
}
}
}
for (int i = 0; i < n; i += n - 1) {
for (int j = 0; j < n; j++)
{
for (int k = -1; k <= 1; k += 2) {
int cnt = 0;
int x = i, y = j;
while (x >= 0 && y >= 0 && x < n && y < n) {
cnt += a[x][y] == 'Q';
x++;
y += k;
}
if (cnt > 1) return false;
}
}
}
return true;
};
auto dfs = [&](this auto&& dfs, int dep, int cnt, int status) -> void {
if (cnt > n) return;
if (dep == n) {
if (cnt == n && check()) ans.push_back(a);
return;
}
for (int i = 0; i < a[dep].size(); i++) {
if (status >> i & 1) continue;
a[dep][i] = 'Q';
dfs(dep + 1, cnt + 1, status | (1 << i));
a[dep][i] = '.';
}
};
dfs(0, 0, 0);
return ans;
}
};dfs，二进制记录历史列的状态