重刷回溯

习题集

题型一：排列、组合、子集相关问题
提示：这部分练习可以帮助我们熟悉「回溯算法」的一些概念和通用的解题思路。解题的步骤是：先画图，再编码。去思考可以剪枝的条件， 为什么有的时候用 used 数组，有的时候设置搜索起点 begin 变量，理解状态变量设计的想法。

  1. 全排列（中等）
  2. 全排列 II（中等）：思考为什么造成了重复，如何在搜索之前就判断这一支会产生重复；
  3. 组合总和（中等）
  4. 组合总和 II（中等）
  5. 组合（中等）
  6. 子集（中等）
  7. 子集 II（中等）：剪枝技巧同 47 题、39 题、40 题；
  8. 第 k 个排列（中等）：利用了剪枝的思想，减去了大量枝叶，直接来到需要的叶子结点；
  9. 复原 IP 地址（中等）
    题型二：Flood Fill
    提示：Flood 是「洪水」的意思，Flood Fill 直译是「泛洪填充」的意思，体现了洪水能够从一点开始，迅速填满当前位置附近的地势低的区域。类似的应用还有：PS 软件中的「点一下把这一片区域的颜色都替换掉」，扫雷游戏「点一下打开一大片没有雷的区域」。

下面这几个问题，思想不难，但是初学的时候代码很不容易写对，并且也很难调试。我们的建议是多写几遍，忘记了就再写一次，参考规范的编写实现（设置 visited 数组，设置方向数组，抽取私有方法），把代码写对。

  1. 图像渲染（Flood Fill，中等）
  2. 岛屿数量（中等）
  3. 被围绕的区域（中等）
  4. 单词搜索（中等）
    说明：以上问题都不建议修改输入数据，设置 visited 数组是标准的做法。可能会遇到参数很多，是不是都可以写成成员变量的问题，面试中拿不准的记得问一下面试官

题型三：字符串中的回溯问题
提示：字符串的问题的特殊之处在于，字符串的拼接生成新对象，因此在这一类问题上没有显示「回溯」的过程，但是如果使用 StringBuilder 拼接字符串就另当别论。
在这里把它们单独作为一个题型，是希望朋友们能够注意到这个非常细节的地方。

  1. 电话号码的字母组合（中等），题解；
  2. 字母大小写全排列（中等）；
  3. 括号生成（中等） ：这道题广度优先遍历也很好写，可以通过这个问题理解一下为什么回溯算法都是深度优先遍历，并且都用递归来写。
    题型四：游戏问题
    回溯算法是早期简单的人工智能，有些教程把回溯叫做暴力搜索，但回溯没有那么暴力，回溯是有方向地搜索。「力扣」上有一些简单的游戏类问题，解决它们有一定的难度，大家可以尝试一下。
  4. N 皇后（困难）：其实就是全排列问题，注意设计清楚状态变量，在遍历的时候需要记住一些信息，空间换时间；
  5. 解数独（困难）：思路同「N 皇后问题」；
  6. 祖玛游戏（困难）
  7. 扫雷游戏（困难）

46. 全排列

数不重复

解体思路

  1. 由于要遍历所有的元素，所以需要记录哪些元素已经被使用
  2. 全排列需要所有的元素，所以需要记录元素个数
  1. class Solution {
  2. private:
  3.     int len_;
  4.     vector<vector<int>> res;
  5.     vector<int> path;
  6.     vector<int> nums;
  7. public:
  8.     vector<vector<int>> permute(vector<int>& nums) {
  9.         len_ = nums.size();
  10.         this->nums = nums;
  11.         vector<bool> vis(len_, false);
  12.         dfs(vis, 0);
  14.         return res;
  15.     }
  17.     void dfs(vector<bool>& vis, int count)
  18.     {
  19.         if (count == len_)
  20.         {
  21.             res.push_back(path);
  22.             return;
  23.         }
  25.         for (int i=0; i<len_; i++)
  26.         {
  27.             if (vis[i]) continue;
  29.             path.push_back(nums[i]);
  30.             vis[i] = true;
  31.             dfs(vis, count+1);
  32.             path.pop_back();
  33.             vis[i] = false;
  35.         }
  36.     }
  37. };

47. 全排列 II

对比上一题

  1. 如何去重（剪枝）
  2. 记得排序
  1. class Solution {
  2. private:
  3.     int len_;
  4.     vector<vector<int>> res;
  5.     vector<int> path;
  6.     vector<int> nums;
  7. public:
  8.     vector<vector<int>> permuteUnique(vector<int>& nums) {
  9.         len_ = nums.size();
  10.         sort(nums.begin(), nums.end());
  11.         this->nums = nums;
  12.         vector<bool> vis(len_, false);
  13.         dfs(vis, 0);
  15.         return res;
  16.     }
  18.     void dfs(vector<bool>& vis, int count)
  19.     {
  20.         if (count == len_)
  21.         {
  22.             res.push_back(path);
  23.             return;
  24.         }
  26.         for (int i=0; i<len_; i++)
  27.         {
  28.             if (vis[i] || (i>0 && nums[i] == nums[i-1] && !vis[i-1]))
  29.                 continue;
  31.             path.push_back(nums[i]);
  32.             vis[i] = true;
  33.             dfs(vis, count+1);
  34.             path.pop_back();
  35.             vis[i] = false;
  37.         }
  38.     }
  39. };

39. 组合总和

本题通过画图， 剪枝条件：是大于target 每次都是从当前元素向后选（因此要排序）

  1. class Solution {
  2. private:
  3.     vector<vector<int>> res_;
  4.     vector<int> candidates_;
  5.     vector<int> combi_;
  6.     int len_;
  7. public:
  8.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
  9.         sort(candidates.begin(), candidates.end());
  10.         candidates_ = candidates;
  11.         len_ = candidates.size();
  13.         dfs(0, target);
  15.         return res_;
  16.     }
  18.     void dfs(int idx, int target)
  19.     {
  20.         if (target == 0){
  21.             res_.push_back(combi_);
  22.             return ;
  23.         }
  25.         for (int i=idx; i<len_&&target-candidates_[i]>=0; i++)
  26.         {
  27.             combi_.push_back(candidates_[i]);
  28.             dfs(i, target-candidates_[i]);
  29.             combi_.pop_back();
  30.         }
  31.     }
  32. };
  1. class Solution {
  2. private:
  3.     vector<vector<int>> res_;
  4.     vector<int> candidates_;
  5.     vector<int> combi_;
  6.     int len_;
  7. public:
  8.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
  9.         sort(candidates.begin(), candidates.end());
  10.         candidates_ = candidates;
  11.         len_ = candidates.size();
  13.         dfs(0, target);
  15.         return res_;
  16.     }
  18.     void dfs(int idx, int target)
  19.     {
  20.         if (target == 0){
  21.             res_.push_back(combi_);
  22.             return ;
  23.         }
  25.         if (idx>=len_ || target-candidates_[idx]<0)
  26.             return ;
  28.         // choose idx
  29.         combi_.push_back(candidates_[idx]);
  30.         dfs(idx, target-candidates_[idx]);
  31.         combi_.pop_back();
  33.         // don't choose idx
  34.         dfs(idx+1, target);
  36.     }
  37. };

40. 组合总和 II

image.png

黑色的圈中是重复的情况，需要剪枝 条件是： 当前元素和前一个相同，且前一个没有使用到 

  1. class Solution {
  2. private:
  3.     vector<vector<int>> res_;
  4.     vector<int> candidates_;
  5.     vector<int> combi_;
  6.     vector<bool> vis_;
  7.     int len_;
  8. public:
  9.     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
  10.         sort(candidates.begin(), candidates.end());
  11.         candidates_ = candidates;
  12.         len_ = candidates.size();
  13.         vis_ = vector<bool>(len_, false);
  15.         dfs(0, target);
  17.         return res_;
  18.     }
  20.     void dfs(int idx, int target)
  21.     {
  22.         if (target == 0){
  23.             res_.push_back(combi_);
  24.             return ;
  25.         }
  27.         for (int i=idx; i<len_&&target-candidates_[i]>=0; i++)
  28.         {
  29.             if (i>0 && candidates_[i] == candidates_[i-1] && !vis_[i-1])
  30.                 continue;
  31.             combi_.push_back(candidates_[i]);
  32.             vis_[i] = true;
  33.             dfs(i+1, target-candidates_[i]);
  34.             vis_[i] = false;
  35.             combi_.pop_back();
  36.         }
  37.     }
  38. };

下面到写法存在问题

  1. class Solution {
  2. private:
  3.     vector<vector<int>> res_;
  4.     vector<int> candidates_;
  5.     vector<int> combi_;
  6.     vector<bool> vis_;
  7.     int len_;
  8. public:
  9.     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
  10.         sort(candidates.begin(), candidates.end());
  11.         candidates_ = candidates;
  12.         len_ = candidates.size();
  13.         vis_ = vector<bool>(len_, false);
  15.         dfs(0, target);
  17.         return res_;
  18.     }
  20.     void dfs(int idx, int target)
  21.     {
  22.         if (target == 0){
  23.             res_.push_back(combi_);
  24.             return ;
  25.         }
  27.         if (
  28.             (idx>0 && candidates_[idx] == candidates_[idx-1] && !vis_[idx-1])
  29.             || (idx >= len_)
  30.             || (target - candidates_[idx] < 0)
  31.         )
  32.             return ;
  34.         combi_.push_back(candidates_[idx]);
  35.         vis_[idx] = true;
  36.         dfs(idx+1, target-candidates_[idx]);
  37.         vis_[idx] = false;
  38.         combi_.pop_back();
  40.         dfs(idx+1, target);
  43.     }
  44. };

[[1,1,6],[1,2,5],[1,7]]

可以从上面的代码分析出，此写法，由于idx的状态无法从第2（3……n）开始，导致回溯到第一个元素就输出了。

77. 组合

本题思路简单 

  1. class Solution {
  2. private:
  3.     vector<vector<int>> res_;
  4.     vector<int> combi_;
  5.     int n_;
  6. public:
  7.     vector<vector<int>> combine(int n, int k) {
  8.         n_ = n;
  10.         dfs(1, k);
  12.         return res_;
  13.     }
  15.     void dfs(int idx, int count)
  16.     {
  17.         if (count == 0){
  18.             res_.push_back(combi_);
  19.             return ;
  20.         }
  22.         for (int i=idx; i<=n_; i++)
  23.         {
  24.             combi_.push_back(i);
  25.             dfs(i+1, count-1);
  26.             combi_.pop_back();
  27.         }
  28.     }
  29. };

这里是可以执行剪枝的

  1. if (idx+count-1 > n_)  return ;    // 剪枝

可以发现，如果没有涉及到重复元素，都可以选择不使用循环，回到某个状态

  1. class Solution {
  2. private:
  3.     vector<vector<int>> res_;
  4.     vector<int> combi_;
  5.     int n_;
  6. public:
  7.     vector<vector<int>> combine(int n, int k) {
  8.         n_ = n;
  10.         dfs(1, k);
  12.         return res_;
  13.     }
  15.     void dfs(int idx, int count)
  16.     {
  17.         if (idx+count-1 > n_)  return ;
  18.         if (count == 0){
  19.             res_.push_back(combi_);
  20.             return ;
  21.         }
  23.         combi_.push_back(idx);
  24.         dfs(idx+1, count-1);
  25.         combi_.pop_back();
  27.         dfs(idx+1, count);
  29.     }
  30. };

78. 子集

  1. class Solution {
  2. private:
  3.     vector<vector<int>> res_;
  4.     vector<int> combi_;
  5.     vector<int> nums_;
  6.     int n_;
  7. public:
  8.     vector<vector<int>> subsets(vector<int>& nums) {
  9.         nums_ = nums;
  10.         n_ = nums.size();
  12.         dfs(0, 0);
  14.         return res_;
  15.     }
  17.     void dfs(int idx, int count) 
  18.     {
  19.         if (count == n_) 
  20.         {
  21.             res_.push_back(combi_);
  22.             return ;
  23.         }
  25.         for (int i=idx; i<n_; i++)
  26.         {
  27.             // don't choose
  28.             dfs(i+1, count+1);
  30.             // chooose
  31.             combi_.push_back(nums_[i]);
  32.             dfs(i+1, count+1);
  33.             combi_.pop_back();
  34.         }
  35.     }
  36. };

受到下一题的启发，哈哈

  1. class Solution {
  2. private:
  3.     vector<vector<int>> res_;
  4.     vector<int> combi_;
  5.     vector<int> nums_;
  6.     int n_;
  7. public:
  8.     vector<vector<int>> subsets(vector<int>& nums) {
  9.         nums_ = nums;
  10.         n_ = nums.size();
  12.         dfs(0);
  14.         return res_;
  15.     }
  17.     void dfs(int idx) 
  18.     {
  19.         res_.push_back(combi_);
  21.         for (int i=idx; i<n_; i++)
  22.         {
  23.             combi_.push_back(nums_[i]);
  24.             dfs(i+1);
  25.             combi_.pop_back();
  26.         }
  27.     }
  28. };

90. 子集 II

  1. class Solution {
  2. private:
  3.     vector<vector<int>> res_;
  4.     vector<int> nums_;
  5.     vector<int> combi_;
  6.     vector<bool> used_;
  7.     int n_;
  8. public:
  9.     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
  10.         sort(nums.begin(), nums.end());
  11.         n_ = nums.size();
  12.         nums_ = nums;
  13.         used_ = vector<bool>(n_, false);
  15.         dfs(0, 0);
  17.         return res_;
  19.     }
  21.     void dfs(int idx, int count)
  22.     {
  23.         if (count == n_)
  24.         {
  25.             res_.push_back(combi_);
  26.             return;
  27.         }
  29.         for (int i=idx; i<n_; i++)
  30.         {
  31.             dfs(i+1, count+1); // this is different
  32.             if (i>0 && nums_[i]==nums_[i-1] && !used_[i-1])
  33.                 continue;
  35.             combi_.push_back(nums_[i]);
  36.             used_[i] = true;
  37.             dfs(i+1, count+1);
  38.             used_[i] = false;
  39.             combi_.pop_back();
  41.         }
  42.     }
  43. };

这里有个不一样到地方，就是将不选在循环的每一步都执行

image.png
通过绘图可以发现，每次dfs时，插入一个元素，得到都是一个子集，只需要注意剪枝即可

  1. class Solution {
  2. private:
  3.     vector<vector<int>> res_;
  4.     vector<int> nums_;
  5.     vector<int> combi_;
  6.     vector<bool> used_;
  7.     int n_;
  8. public:
  9.     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
  10.         sort(nums.begin(), nums.end());
  11.         n_ = nums.size();
  12.         nums_ = nums;
  13.         used_ = vector<bool>(n_, false);
  15.         dfs(0);
  17.         return res_;
  19.     }
  21.     void dfs(int idx)
  22.     {
  23.         res_.push_back(combi_);
  25.         for (int i=idx; i<n_; i++)
  26.         {
  27.             if (i>0 && nums_[i]==nums_[i-1] && !used_[i-1])
  28.                 continue;
  30.             combi_.push_back(nums_[i]);
  31.             used_[i] = true;
  32.             dfs(i+1);
  33.             used_[i] = false;
  34.             combi_.pop_back();
  36.         }
  37.     }
  38. };

60. 排列序列

看到题目直接就想起了直接递归到第k个然后给出答案，哈哈哈

  1. class Solution {
  2. public:
  3.     string getPermutation(int n, int k) {
  4.         stringstream ss;
  5.         for (int i=1; i<=n; i++)
  6.             ss << i;
  8.         if (k == 1) return ss.str();
  10.         int i = 1;
  11.         string s1 = ss.str(), res;
  12.         while (next_permutation(s1.begin(), s1.end()))
  13.         {
  14.             if (++i == k) {
  15.                 res = s1;
  16.                 break;
  17.             }
  19.         }
  21.         return res;
  22.     }
  23. };

image.png
注意两点

  1. 第k个数实际上是第k-1个（这里应该是从0开始的原因吧，猜测）
  2. 可以看到每次取start的值时，需要在前一次将数组从使用过的地方前移。
  1. class Solution {
  2. public:
  3.     string getPermutation(int n, int k) {
  4.         vector<int> nums(n);
  5.         iota(nums.begin(), nums.end(), 1);
  6.         k--;
  8.         string res;
  10.         while (n--)
  11.         {
  12.             int cur_layer_num = factorial(n);
  13.             int start = k / cur_layer_num;
  14.             k %= cur_layer_num;
  15.             res.push_back(nums[start] + '0');
  17.             // 将数组从使用到到数开始向前移动
  18.             for (int j=start; j<n; j++)
  19.                 nums[j] = nums[j+1];
  21.         }
  23.         return res;
  24.     }
  26.     int factorial(int n)
  27.     {
  28.         if (n == 0) return 1;
  30.         return n * factorial(n-1);
  31.     }
  32. };

这个思路借鉴的是比较符合我的思路的

93. 复原 IP 地址

  2. class Solution {
  3. private:
  4.         string s;
  5.         vector<string> combi;
  6.         vector<string> res;
  7. public:
  8.     vector<string> restoreIpAddresses(string s) {
  9.         this->s = s;
  11.         dfs(0, s);
  12.         return res;
  14.     }
  16.     void dfs(int count, string remainStr)
  17.     {
  19.         if (count == 3 && isValid(remainStr))
  20.         {
  21.             res.push_back(vec2str(combi)+remainStr);
  22.             return ;
  23.         }
  25.         for (int i=1; i<=3&&i<=remainStr.size(); i++)
  26.         {
  27.             string cur = remainStr.substr(0, i);
  28.             if (isValid(cur))
  29.             {
  30.                 combi.push_back(cur + ".");
  31.                 dfs(count+1, remainStr.substr(i));
  32.                 combi.pop_back();
  33.             }
  34.         }
  35.     }
  38.     bool isValid(string& s)
  39.     {
  40.         if (s=="" || s.size()>1 && s[0]=='0') return false;
  41.         long num = stol(s);
  42.         return (num>=0 && num<=255);
  43.     }
  45.     string vec2str(const vector<string>& v)
  46.     {
  47.         string res;
  48.         for (auto &i : v)
  49.             res += i;
  50.         return res;
  51.     }
  54. };

这里的写法是借鉴剑指offer中的写法

解题的时候需要注意的点

  1. 0开头的需要排除
  2. 判断是否合理时：
    1. “”空字符串的情况
    2. 0*这种情况（如03.1.1.1）
  1. class Solution {
  2. public:
  4.     vector<string> restoreIpAddresses(string s) {
  5.         // write code here
  6.         vector<string> result;
  7.         string curAns;
  8.         dfs(s, result, curAns, 0); //需不需要循环要根据具体的情况而定。
  9.         return result; 
  10.     }
  13.     void dfs(string remainString, vector<string>& ans, string curAns, int count)
  14.     {
  15.         /*回溯出口*/
  16.         if (count==3 && valid(remainString))/*IP address only contain 4 parts*/
  17.         {
  18.             ans.emplace_back(curAns + remainString);
  19.             return;
  20.         }
  23.         for (int i = 1; i < remainString.size()&&i<4; ++i)
  24.         {
  25.             string sub = remainString.substr(0,i);
  26.             if (valid(sub))
  27.                 dfs(remainString.substr(i), ans, curAns+sub+".", count + 1);
  28.         }
  29.     }
  31.     bool valid(string& s)
  32.     {
  33.         /*0-255合法
  34.         01，这种前面的0是不合法的
  35.         */
  36.         if (s.size() > 1 && s[0] == '0')
  37.             return false;
  38.         // stoi 会爆int
  39.         return stol(s) >= 0 && stol(s) <= 255;
  40.     }
  43. };

733. 图像渲染

这里我纠结了很久x和y 的表示 /doge

注意一开始

  1. class Solution {
  2.     vector<pair<int, int>> moves{{-1,0}, {1, 0}, {0, -1}, {0, 1}};
  3.     int m, n;
  4.     int newColor, oldColor;
  5. public:
  6.     vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
  7.         n = image[0].size(), m = image.size(); // n:y m:x
  8.         this->newColor = newColor;
  9.         oldColor =  image[sr][sc];
  11.         if (newColor != oldColor)
  12.             dfs(image, sr, sc);
  13.         return image;
  14.     }
  16.     void dfs(vector<vector<int>>& image, int sr, int sc)
  17.     {
  18.         image[sr][sc] = newColor;
  19.         for (int i=0; i<4; i++)
  20.         {
  21.             int dx = sr + moves[i].first, dy = sc + moves[i].second;
  22.             if (dx>=0 && dx<m && dy>=0 && dy<n && oldColor==image[dx][dy])
  23.                 dfs(image, dx, dy);
  24.         }
  25.     }
  26. };

200. 岛屿数量

思路： 刚开始在如何记录岛屿的数量上犯难， 后面想到，用dfs将走到过的位置标记，每一次dfs，会将岛屿包含的所以的点都标记 然后遍历每一个点，如果遇到没有标记的陆地，则是新的岛屿，岛屿数量+1；

  1. class Solution {
  2. private:
  3.     int dx[4] = {-1, 1, 0, 0};
  4.     int dy[4] = { 0, 0, -1, 1};
  5.     int m, n;
  6.     int res{0};
  7.     vector<vector<bool>> vis;
  8. public:
  9.     int numIslands(vector<vector<char>>& grid) {
  10.         printVec(grid);
  11.         m = grid.size(), n = grid[0].size();
  12.         vis = vector<vector<bool>>(m, vector<bool>(n, false));
  13.         for (int i=0; i<m; i++)
  14.         {
  15.             for (int j=0; j<n; j++)
  16.             {
  17.                 if (!vis[i][j] && grid[i][j]=='1')
  18.                 {
  19.                     res++;
  20.                     dfs(grid, i, j);
  21.                 }
  22.             }
  23.         }
  24.         return res;
  26.     }
  28.     void dfs(vector<vector<char>>& grid,int x, int y)
  29.     {
  30.         vis[x][y] = true;
  31.         for (int k=0; k<4; k++)
  32.         {
  33.            int dxx, dyy;
  34.            dxx = x + dx[k], dyy = y + dy[k];
  35.            if (dxx>=0 && dxx<m && dyy>=0 && dyy<n && !vis[dxx][dyy] && grid[dxx][dyy]=='1')
  36.                dfs(grid, dxx, dyy);
  37.         }
  39.     }
  40. };

130. 被围绕的区域

思路

从四周向中间遍历，最后没有被访问到地方就是被围绕到区域

本题有两个需要注意的情况：

  • 最后被围绕到有可能是非陆地
  • 周围陆地相邻的陆地也是岛屿
  1. class Solution {
  2.     vector<vector<bool>> vis;
  3.     int m, n;
  4.     int dx[4] = {-1, 1, 0, 0};
  5.     int dy[4] = {0, 0, -1, 1};
  7. public:
  8.     void solve(vector<vector<char>>& board) {
  10.         m = board.size(), n = board[0].size();
  11.         vis = vector<vector<bool>>(m, vector<bool>(n, false));
  13.         for (int i=0; i<m; i++)
  14.             dfs(board, i, 0, board[i][0]), dfs(board, i, n-1, board[i][n-1]);
  16.         for (int j=0; j<n; j++)
  17.             dfs(board, 0, j, board[0][j]), dfs(board, m-1, j, board[m-1][j]);
  19.         for (int i=1; i<m-1; i++)
  20.             for (int j=1; j<n-1; j++)
  21.                 if(!vis[i][j] && board[i][j]=='O')  board[i][j] = 'X';
  23.     }
  25.     void dfs(vector<vector<char>>& board, int  x, int y, char c)
  26.     {
  27.         vis[x][y] = true;
  29.         for (int i=0; i<4; i++)
  30.         {
  31.             int dxx, dyy;
  32.             dxx = x + dx[i], dyy = y + dy[i];
  33.             if (dxx>=0 && dxx<m && dyy>=0 && dyy<n && !vis[dxx][dyy] && board[dxx][dyy]==c)
  34.                 dfs(board, dxx,dyy, c);
  35.         }
  36.     }
  37. };

79. 单词搜索

在写的时候多次忘记了回溯访问状态，哈哈

前面的题目都不需要回溯，本题需要

class Solution {
    int m, n;
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    vector<vector<char>> board;
    string word;
    bool res{false};
public:
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size(), n = board[0].size();
        this->board = board;
        this->word = word;

        for (int i=0; i<m; i++)
        {
            for (int j=0; j<n; j++)
            {
                if (board[i][j] != word[0]) continue;
                vector<vector<bool>> vis(m, vector<bool>(n, false));
                dfs(vis, i, j, 0);
                if (res) return true;
            }
        }
        return false;
    }

    void dfs(vector<vector<bool>>& vis, int x, int y, int idx)
    {
        if (idx == word.size()-1) res = true;

        vis[x][y] = true;

        for (int i=0; i<4; i++)
        {
            int dxx, dyy;
            dxx = dx[i] + x, dyy = dy[i] + y;

            if (dxx>=0 && dxx<m && dyy>=0 && dyy<n && !vis[dxx][dyy] && board[dxx][dyy]==word[idx+1])
                dfs(vis, dxx, dyy, idx+1);

        }
        vis[x][y] = false; // backtrace is important

    }

};

17. 电话号码的字母组合

这题和全排列很像

class Solution {
private:
    int n;
    vector<string> res;
    string combi;
    unordered_map<char, string> mp{{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5',"jkl"}, {'6', "mno"}, {'7',"pqrs"}, {'8', "tuv"}, {'9',"wxyz"}};
public:
    vector<string> letterCombinations(string digits) {
        if (digits == "") return {};

        n = digits.size();
        dfs(digits, 0);

        return res;
    }

    void dfs(string& digits, int idx)
    {
        if (idx == n)
        {
            res.push_back(combi);
            return;
        }

        string curStr = mp[digits[idx]];
        for (int i=0; i<curStr.size();i++)
        {
            combi.push_back(curStr[i]);
            dfs(digits, idx+1);
            combi.pop_back();
        }
    }
};

22. 括号生成

虽然写出来了，但是代码有点丑 \dog

class Solution {
private:
    string s;
    vector<string> res;
    string combi;
    int n;
public:
    vector<string> letterCasePermutation(string s) {
        n = s.size();
        this->s = s;

        dfs(0);

        return res;

    }

    void dfs(int idx)
    {
        if (idx == n)
        {
            res.push_back(combi);
            return ;
        }

        char ch = s[idx];
        combi.push_back(ch);
        dfs(idx+1);
        combi.pop_back();

        if (islower(ch))
        {
            ch = toupper(ch);
            combi.push_back(ch);
            dfs(idx+1);
            combi.pop_back();
        }
        else if (isupper(ch))
        {
            ch = tolower(ch);
            combi.push_back(ch);
            dfs(idx+1);
            combi.pop_back();
        }

    }
};

22. 括号生成

这里有一个需要注意的点是：先“（” 后 “）” ==》 当前的结果中，左括号一定是大于等于右括号的

class Solution {
private:
    vector<string> res;
    string combi;
    int n;
public:
    vector<string> generateParenthesis(int n) {
        this->n = n;

        dfs(0, 0);

        return res;

    }

    void dfs(int cnt1, int cnt2)
    {
        if (cnt1==n && cnt2==n)
        {
            res.push_back(combi);
            return;
        }

        if (cnt1 < n)
        {
            combi.push_back('(');
            dfs(cnt1+1, cnt2);
            combi.pop_back();
        }

        if (cnt2<n && cnt2<cnt1)
        {
            combi.push_back(')');
            dfs(cnt1, cnt2+1);
            combi.pop_back();
        }
    }
};

51. N 皇后

yxc yyds

class Solution {
    int N;
    vector<bool> dg, udg, rows;
    vector<vector<string>> res;
    vector<string> combi;

public:
    vector<vector<string>> solveNQueens(int n) {
        N = n;
        dg = vector<bool>(2*n, false);
        udg = vector<bool>(2*n, false);
        rows = vector<bool>(n, false);
        combi = vector<string>(n, string(n, '.'));

        dfs(0);

        return res;

    }

    void dfs(int row)
    {
        if (row == N)
        {
            res.push_back(combi);
            return;
        }

        for (int col=0; col<N; col++)
        {
            if (!rows[col] && !dg[col+row] && !udg[row+N-col])
            {
                combi[row][col] = 'Q';
                rows[col] = dg[col+row] = udg[row+N-col] = true;
                dfs(row+1);
                rows[col] = dg[col+row] = udg[row+N-col] = false;
                combi[row][col] = '.';

            }
        }
    }
};