本文主要是介绍hot100 -- 回溯（下），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
👂 ▶ 幸福就是 (163.com)
👂 ▶ 当爱在靠近 (163.com)
目录
🚩括号生成
AC DFS
🌼单词搜索
AC DFS
🎂分割回文串
AC DFS+DP
AC DFS+记忆化
🌼N 皇后
AC DFS
🚩括号生成
22. 括号生成 - 力扣（LeetCode）
AC DFS
class Solution {
private:string temp; // 临时答案vector<string> ans;void dfs(int n, int l, int r) { // 左括号数 l, 右括号数 r// 递归出口if (temp.size() == 2*n) {ans.push_back(temp);return;}// 递归if (l < n) {temp.push_back('(');dfs(n, l + 1, r);temp.pop_back(); // 回溯时取消标记}if (r < l) { // 为了保证匹配，这里 r < l，保证左边的 '(' 匹配 右边的 ')'temp.push_back(')');dfs(n, l, r + 1);temp.pop_back();}}
public:vector<string> generateParenthesis(int n) {dfs(n, 0, 0);return ans;}
};🌼单词搜索
79. 单词搜索 - 力扣（LeetCode）
AC DFS
每个点 DFS 一次，有任一路径满足即可
class Solution {
private:int nex[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; // 4 个方向int vis[8][8];// (x, y) 开始, word 中第 count 个字符bool dfs(int x, int y, int count, vector<vector<char>>& board, string word) {int num = word.size(), m = board.size(), n = board[0].size();// 递归出口if (board[x][y] != word[count])return false;if (count == num - 1) return true;vis[x][y] = 1; // 标记int result = 0;// 递归for (int i = 0; i < 4; ++i) {int xx = x + nex[i][0], yy = y + nex[i][1];if (xx >= 0 && xx < m && yy >= 0 && yy < n && !vis[xx][yy]) { // 未越界 && 未访问int flag = dfs(xx, yy, count + 1, board, word); // 递归 if (flag) {result = 1;break;}}}vis[x][y] = 0; // 取消标记return result;}
public:bool exist(vector<vector<char>>& board, string word) {int m = board.size(), n = board[0].size();// 从每一个点开始 DFSfor (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) {int flag = dfs(i, j, 0, board, word);if (flag) return true;}return false;}
};🎂分割回文串
131. 分割回文串 - 力扣（LeetCode）
AC DFS+DP
1）常规判断回文，用双指针 O(n)，这里采用 DP O(1)👇
a. 含义：dp[i][j] == 1，字符串片段 [i, j] 是回文串
b. 递推式：dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1]
c. 初始化：全部初始化为 1，两层 for 循环中，加个 s[i] == s[j] 的条件即可
d. 遍历顺序：根据递推式，且考虑到 i <= j，i 由 i + 1 得到，i 从 i = n - 1 开始遍历，j 从 i 开始
2）注意递归 dfs(s, j + 1)，而不是 dfs(s, x + 1)，因为当前 [x, j] 部分已经分割出来，并插入 temp 了，下一部分应该从 j + 1 开始
3）坑：第 33 行，dp 递推那里，j = i + 1 开始，否则当 i = 0, j = i = 0，此时 j - 1 == -1，会出现 dp[1][-1] 导致溢出
时间 O(n * 2^n)
O(n) 字符串长度
O(2^n) 长度为 n 的字符串划分方案数 2^(n-1) ≈ O(2^n)
class Solution {
private:vector<string> temp; // 临时答案vector<vector<string>> ans;vector<vector<int>> dp;int n; // 字符串 s 长度// 分割字串 [x, ...]void dfs(string s, int x) {// 递归出口：字符串末尾, 分割完毕if (x == n) {ans.push_back(temp);return;}// [x, x] ... [x, n-1]for (int j = x; j < n; ++j) {if (dp[x][j]) { // 回文temp.push_back(s.substr(x, j - x + 1));// [x, j] -> [j + 1, ...]// 递归分割下一部分dfs(s, j + 1);temp.pop_back(); // 回溯 恢复现场}}}
public:vector<vector<string>> partition(string s) {n = s.size();// 初始化 dp 为 1dp.resize(n, vector<int>(n, 1)); // 等价于 assign// dp 递归式for (int i = n - 1; i >= 0; --i)for (int j = i + 1; j < n; ++j) // j = i + 1 开始，防止 i = 0 时 溢出dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1];dfs(s, 0); // 下标 0 开始分割 [0, ...]return ans; }
};AC DFS+记忆化
将上面 O(1) 的 dp 变成 DFS 中的记忆化，本质一样，都是通过记录已有的结果，减少重复计算
记忆化一般用递归 return 实现
比 DP O(1) 求回文，慢很多
class Solution {
private:vector<string> temp; // 临时答案vector<vector<string>> ans;vector<vector<int>> dp;int n; // 字符串 s 长度// 分割字串 [x, ...]void dfs(string s, int x) {// 递归出口：字符串末尾, 分割完毕if (x == n) {ans.push_back(temp);return;}// [x, x] ... [x, n-1]for (int j = x; j < n; ++j) {if (isParlin(x, j, s) == 1) { // 回文temp.push_back(s.substr(x, j - x + 1));// [x, j] -> [j + 1, ...]// 递归分割下一部分dfs(s, j + 1);temp.pop_back(); // 回溯 恢复现场}}}// 记忆化搜索判断回文// 0 未搜索 1 回文 -1 非回文int isParlin(int l, int r, string s) {if (dp[l][r])return dp[l][r]; // 返回已有结果if (l >= r) return dp[l][r] = 1; // 一个元素--回文return dp[l][r] = (s[l] == s[r]) ? isParlin(l+1, r-1, s) : -1;}
public:vector<vector<string>> partition(string s) {n = s.size();dp.resize(n, vector<int>(n)); // 初始化为 0dfs(s, 0); // 下标 0 开始分割 [0, ...]return ans; }
};🌼N 皇后
51. N 皇后 - 力扣（LeetCode）
AC DFS
col[] 标记列，dfs(int r) 参数 r 标记行
两个点，行差值的绝对值 == 列差值的绝对值，表示（左斜 OR 右斜）冲突
由此，行，列，左斜，右斜是否冲突就可得到
取消标记时，只需要恢复 col[]（对列的标记），而不需要恢复 a[]（放置位置），因为 a[] 会被后续操作覆盖，但是 col 不会，需要手动恢复现场
坑：int flag = 0; 这个要放在 if(c[j] == 0) 里，如果放在外面，就算列已经被占了，也会进入下一步递归，平白多了许多无关结果
class Solution {
private:vector<string> temp; // 临时答案vector<vector<string>> ans;int m;int c[10]; // 标记该列（已放置）int a[10]; // 位置, a[3] = 7 表示 (3, 7) 已放置// 第 r 行, 已放置 r 个皇后void dfs(int r) {// 递归出口if (r == m) {ans.push_back(temp);return;}// 遍历每一列for (int j = 0; j < m; ++j) {if (c[j] == 0) { // 这一列未放置int flag = 0; // 标记左斜 / 右斜 冲突for (int i = 0; i < r; ++i) // 遍历前面已放置的每一行if (abs(r - i) == abs(j - a[i])) {flag = 1;break;}// 不冲突，(r, j) 可以放置if (flag == 0) {a[r] = j; // 放置string s = string(m, '.');s[j] = 'Q';temp.push_back(s);c[j] = 1; // 标记（列）dfs(r + 1); c[j] = 0; // 取消标记temp.pop_back(); // 恢复现场}}}}
public:vector<vector<string>> solveNQueens(int n) {m = n; // m 个皇后dfs(0);return ans;}
};这篇关于hot100 -- 回溯（下）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
