失眠网 > LeetCode刷题系列(一)把回溯算法框架将给爷爷奶奶听

LeetCode刷题系列(一)把回溯算法框架将给爷爷奶奶听

时间：2023-11-08 20:00:10

文章目录

回溯求解框架基于回溯框架求解之全排列基于回溯框架求解之全排列 II基于回溯框架求解之子集基于回溯框架求解之子集 II基于回溯框架求解之二进制手表基于回溯框架求解之分割回文串基于回溯框架求解之八皇后基于回溯框架求解之单词搜索基于回溯框架求解之解数独参考

文章目录

回溯求解框架

在回溯算法套路详解中，作者给出了一个回溯算法的框架：

result = []def backtrack(路径, 选择列表):if 满足结束条件:result.add(路径)returnfor 选择 in 选择列表:判断是否需要剪枝做选择backtrack(路径, 选择列表)撤销选择

上面这个真的就是个框架，有几个需要注意的点：1.回溯函数的参数是什么，怎么定？2.结束条件需要依据题意来确定；3.在进入for循环遍历选择之后还需要判断是否需要剪枝。4.在选择列表中做出选择。5.进入递归，进入下一层递归树。6.撤销选择，去穷举另外一个选择。

基于回溯框架求解之全排列

说这么多也没什么用，结合一个例子来说明：比如Leetcode第46题全排列：给定一个没有重复数字的序列，返回其所有可能的全排列。示例：

输入: [1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

我习惯先考虑主逻辑，也就是for循环内部如何工作，然后去补充上面提到的5个注意点，那么主逻辑就是我们每次都可以从[1,2,3]中做出选择，选择这个节点是否需要加入到我们的临时结果中。因为做完这个选择之后，我们还要遍历其它的选择，因此最后还需要撤销这个选择。这个撤销的理解就是，比如第一次循环我们选择了数字1，那么下一次就是选择2了，而1这个选择我们就需要撤销，此时的for循环就可以写成：

void backtrack(vector<int>& nums, vector<int>& path){for(int i=0; i<nums.size(); ++i){path.push_back(nums[i]);backtrack(nums, path);path.pop_back();}}

初步的想法就形成了，不断地对数组中的数字进行组合，可以看作树的一个全展开递归调用。上述代码还是有一些小问题的，最明显的就是这个会无限递归下去，因此我们首先可以加上结束条件：

void backtrack(vector<int>& nums, vector<int>& path){if(path.size() == nums.size()){res.push_back(path);return;}for(int i=0; i<nums.size(); ++i){path.push_back(nums[i]);backtrack(nums, path);path.pop_back();}}

因为这里每次循环都是从0开始，也就是每次都会遍历整个数组，比如会出现添加了[1, 1, 1]的这种情况，注意到题目给定的条件，是一个没有重复数字的序列。因此当一个元素被选定添加到path数组中之后，我们就不能在下一层中再次选择它，为了实现上述的这个功能，我们可以设置一个集合s，用来记录已经被选择过的元素，如果新加入的元素在集合中的话，我们就不用再往下走了，相当于一个剪枝的过程：

void backtrack(vector<int>& nums, vector<int>& path, unordered_set<int>& s){if(path.size() == nums.size()){res.push_back(path);return;}for(int i=0; i<nums.size(); ++i){if(s.count(nums[i])) continue;s.insert(nums[i]);path.push_back(nums[i]);backtrack(nums, path, s);s.erase(nums[i]);path.pop_back();}}

到此回溯的整个代码就写完了，整体代码如下：

class Solution {public:vector<vector<int>> res;vector<vector<int>> permute(vector<int>& nums) {vector<int> path;unordered_set<int> s;backtrack(nums, path, s);return res;}void backtrack(vector<int>& nums, vector<int>& path, unordered_set<int>& s){if(path.size() == nums.size()){res.push_back(path);return;}for(int i=0; i<nums.size(); ++i){if(s.count(nums[i])) continue;s.insert(nums[i]);path.push_back(nums[i]);backtrack(nums, path, s);s.erase(nums[i]);path.pop_back();}}};

这里我们是用了一个集合来记录被访问过的元素，之后好用于剪枝，我们也可以用别的方式来记录已经被访问过的元素，比如像数组，这里可能就会有小伙伴问了，用集合就可以了，为什么还要用数组呢？其实用数组的解法更加通用一点，因为如果遇到了数组中有重复元素的话，那我们用集合的话就不方便去记录哪个元素被访问过了什么的。因此我们把集合换成数组就可以得到另一种解法：

class Solution {public:vector<vector<int>> res;vector<vector<int>> permute(vector<int>& nums) {vector<int> path;vector<int> vis(nums.size(), 0);backtrack(nums, path, vis);return res;}void backtrack(vector<int>& nums, vector<int>& path, vector<int>& vis){if(path.size() == nums.size()){res.push_back(path);return;}for(int i=0; i<nums.size(); ++i){if(vis[i]) continue;vis[i] = 1;path.push_back(nums[i]);backtrack(nums, path, vis);vis[i] = 0;path.pop_back();}}};

基于回溯框架求解之全排列 II

既然说到了数组中有重复元素的情况，那就来看一下这个全排列的进阶：Leetcode47全排列 II：给定一个可包含重复数字的序列nums，按任意顺序返回所有不重复的全排列。举例如下：

输入：nums = [1,1,2]输出：[[1,1,2],[1,2,1],[2,1,1]]

依据之前的所述，我们可以很容易写出整颗递归树的全展开形式：

问题的关键就在于剪枝的过程。首先第一点被访问过的元素应该被剪枝，这个可以采用一个数组来记录哪些元素已经被访问过了，访问过了的元素就剪枝即可，这一点与第一道全排列一样。不同点在于现在数组中有重复元素，比如像两个相邻的[1, 1]先访问哪一个后访问哪一个是没有关系的。我们只需要去保证这种情况只会被访问一次即可，其它的情况就剪枝，我们先按照顺序情况求解即可，这里的顺序情况说的是，比如说重复的元素按照从左往右顺序取一遍即可。

那么它满足的条件就是当前元素要等于上一个元素，并且上一个元素被访问过了，没被访问过的话就说明不是顺序取值的情况，需要跳过。而这种情况的满足需要一个前提，就是相同的元素需要排列在一起，我们可以得到如下代码：

class Solution {public:vector<vector<int>> res;vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());vector<int> vis(nums.size(), 0);vector<int> path;backtrack(nums, path, vis);return res;}void backtrack(vector<int>& nums, vector<int>& path, vector<int>& vis){if(path.size() == nums.size()){res.push_back(path);return;}for(int i=0; i<nums.size(); ++i){if(vis[i] || i>0 && nums[i]==nums[i-1] && !vis[i-1]){continue;}vis[i] = 1;path.push_back(nums[i]);backtrack(nums, path, vis);path.pop_back();vis[i] = 0;}}};

上述代码中的最难理解的部分可能就是剪枝部分的代码了：

if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {continue;}

这里较难理解的就是这段代码，其实就是一个剪枝的过程。我们举个例子，来说明!vis[i - 1]这一项：假设我们有两个1的数组，为了加以区分我们把它设置成[1_1, 1_2]，把这两个元素的递归树全展开我们可以得到2×2=42 \times 2=42×2=4种情况：

[1_1, 1_1][1_1, 1_2][1_2, 1_1][1_2, 1_2]

上述四种情况的第一种[1_1, 1_1]中的第二个1_1来自第二轮循环中i等于0的情况，而第二次访问i=0的时候，vis[i]已经被置1了，所以continue跳过，回溯到上一个节点。上述四种情况的第二种[1_1, 1_2]中的1_2来自第二轮循环中i等于1的情况，此时(i > 0 && nums[i] == nums[i - 1])满足条件，但是vis[i-1]表示第一个1_1是否被访问过，它被访问过，所以vis[i-1]=1，因此!vis[i-1]=0，条件不满足，[1_1, 1_2]这一条会被选中。上述四种情况的第三种[1_2, 1_1]来自第一轮循环选中1_2的情况，注意此时已经回溯回去了，此时的1_1的访问标记位vis[0]=0，未被访问过，并且i=1。所以我们需要看后面的条件(i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])，此时i > 0 && nums[i] == nums[i - 1]条件都满足，vis[i-1]=vis[1-1]=vis[0]=0，!vis[i-1]=1条件满足，选择continue跳过，回溯到上一个节点。上述四种情况的第四种[1_2, 1_2]，中的第二个1_2来自第二轮循环中i等于1的情况，而第二次访问i=0的时候，vis[i]=vis[1]=1已经被置1了，所以continue跳过，回溯到上一个节点。

if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {continue;}

而把上述代码中的!vis[i-1]改为vis[i-1]的话也是可以的，此时就相当于把第2和第3中的结果互换一下。就相当于两个重复元素，一个从前往后添加进数组中一个从后往前添加进数组中。从前往后的话就是[1_1, 1_2]这种情况，从后往前的话就是[1_2, 1_1]这种情况。

基于回溯框架求解之子集

上文说的是将整棵递归树全部展开，然后找到剪枝条件进行剪枝。但是有一类问题就不是很适合用递归树的全展开，比如像Leetcode78. 子集问题：给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集，你可以按任意顺序返回解集。示例1：

输入：nums = [1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

如果我们把上述的这个数组按照递归树全展开的话，剪枝将会变得非常复杂，因为需要判断数组之间是不是有重复的，比如说子集[1, 2]和子集[2, 1]就是一样的。因为题目给定的数组中的元素互不相同，所以当一个元素被选中之后，下一层的展开需要去掉这个元素，此时博弈树的展开循环可以写成如下形式：

void backtrack(vector<int>& nums, vector<int>& path, int index){for(int i=index; i<nums.size(); ++i){path.push_back(nums[i]);backtrack(nums, path, i+1);path.pop_back();}}

这里的展开树与之前的展开树的主要区别在于加了一个index选项来判定循环的起始位置，一旦有一个元素被确定了之后，剩下的递归树的展开只能是剩余元素的展开，比如确定了1这个元素被选中，剩下的元素只能在[2, 3]里面去选。并且这样的展开不需要剪枝，所以每一次把path中的结果添加进最终的结果里面即可：

void backtrack(vector<int>& nums, vector<int>& path, int index){res.push_back(path);for(int i=index; i<nums.size(); ++i){path.push_back(nums[i]);backtrack(nums, path, i+1);path.pop_back();}}

最终的代码如下所示：

class Solution {public:vector<vector<int>> res;vector<vector<int>> subsets(vector<int>& nums) {vector<int> path;backtrack(nums, path, 0);return res;}void backtrack(vector<int>& nums, vector<int>& path, int index){res.push_back(path);for(int i=index; i<nums.size(); ++i){path.push_back(nums[i]);backtrack(nums, path, i+1);path.pop_back();}}};

对于上述代码如果理解起来还是比较困难的话，可以参考一下输出结果来进行理解，比如输入nums数组[1,2,3]，输出结果为：

[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]。

基于回溯框架求解之子集 II

对于这个求子集问题，如果给定的数组中有重复元素的话，我们就需要剪枝了。剪枝的方法和之前求全排列中有重复元素的方法是类似的，但不是一样的。回忆一下求子集问题1，在展开递归树的时候下一层的递归树展开是从剩余元素中展开的，因此如果剩余元素中有两个一样的元素的话，我们只需要一个，另一个就需要去剪枝，举个例子，在子集问题1中输入数组nums数组[1,2,3]，输出结果为：

[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]。

如果我们把输入数组[1,2,3]变成[1,2,2]的话，并不进行剪枝，我们只需要把结果中的3，换成2即可，可以得到结果：[[],[1],[1,2],[1,2,2],[1,2],[2],[2,2],[2]]。可以看到[1,2]和[2]重复了。那这两个重复的元素有没有什么共性呢？有！比如像[1,2]第二次出现的时候，就是没有访问第一个2，而跳过来访问第二个2，导致和访问第一个2的时候的[1,2]重复了。而第二次访问得到[2]的时候也是因为，第一次访问第一个2的时候和第二次访问第二个2的时候重复了。因此总结可得剪枝条件就是：前面一个元素与当前元素的值相等，并且前面那个元素没有被访问过就剪枝，这样就能把上述两种情况剪枝掉。留下的其实就是顺序访问得到的结果。这里还需要设置一个数组来记录哪些元素被访问过。剪枝条件可以写成如下形式：

if(i>0 && nums[i]==nums[i-1] && !vis[i-1]){continue;}

整体代码如下：

class Solution {public:vector<vector<int>> res;vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end());vector<int> path;vector<int> vis(nums.size(), 0);backtrack(nums, path, vis, 0);return res;}void backtrack(vector<int>& nums, vector<int>& path, vector<int>& vis, int index){res.push_back(path);for(int i=index; i<nums.size(); ++i){if(i>0 && nums[i]==nums[i-1] && !vis[i-1]){continue;}vis[i] = 1;path.push_back(nums[i]);backtrack(nums, path, vis, i+1);vis[i] = 0;path.pop_back();}}};

这里我想重复一点就是：剪枝的方法和之前求全排列中有重复元素的方法是类似的，但不是一样的。不一样的地方在于没办法从后往前取到元素，因为被index被限制了，for循环并不是每次从0开始for循环的。

基于回溯框架求解之二进制手表

上文我们已经描述了，回溯算法的基本框架，大部分的题目都是基于上述框架的，有些题目你可能会说，哎呀，你这个回溯算法的复杂度太高了，我有复杂度更低的解法。。。下面来看一些加了花里胡哨操作的题目，如果你对回溯算法理解不深入的话，就很难有思路。比如像Leetcode401. 二进制手表：二进制手表顶部有4个LED代表小时（0-11），底部的6个LED代表分钟（0-59）。每个LED代表一个0或1，最低位在右侧。

例如，上面的二进制手表读取 “3:25”。给定一个非负整数n代表当前LED亮着的数量，返回所有可能的时间。示例：

输入: n = 1返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

好，题目就是给这么多信息了。这居然是一道Easy题，题目的意思就是从10个灯里面选n个灯嘛，然后将其组成字符串，然后返回。当然这里还需要去判断这个选的灯有没有超出边界什么的。那我们首先来个回溯把灯给选了好了，因为选过的灯就不必再选了，所以递归树不用每次从i=0开始，从下一层index开始即可，因此此时的回溯算法核心代码可以写成如下形式：

void backtrack(vector<int> &path, int turnedOn, int index){if(path.size() == turnedOn){处理path将其转化为字符串，并将合法结果添加到最终结果中return;}for(int i=index; i<10; ++i){path.push_back(i);backtrack(path, turnedOn, i+1);path.pop_back();}}

可以看到递归树的展开还是比较简单的，其中turnedOn就是n的值。我们拿到了选中的灯path之后，就需要将其转化为time时间了，可以写一个函数来实现这个功能：

unordered_map<int,int> hash={{0,1},{1,2},{2,4},{3,8},{4,1},{5,2},{6,4},{7,8},{8,16},{9,32}};string get_time(vector<int> path){pair<int,int> time(0,0); // 初始化时间for(int i : path){// 循环将被选中的灯的数值加到time里面去if(i<4) time.first+=hash[i];else time.second+=hash[i];}if(time.first>11||time.second>59)//判断合法性，不合法的话返回空的字符串return "";string hour = to_string(time.first); // 将小时转化为字符串string minute = to_string(time.second); // 将分钟转化为字符串if(minute.size() == 1) minute.insert(0, "0"); // 判断分钟前面是否要加个0return hour+":"+minute; // 返回处理后的时间字符串}

这下处理path里面时间的函数也有了，我们就可以得到整个回溯算法核心的逻辑代码了：

void backtrack(vector<int> &path, int turnedOn, int index){if(path.size() == turnedOn){string tmp_res = get_time(path);if(tmp_res.size() > 0){res.push_back(tmp_res);}return;}for(int i=index; i<10; ++i){path.push_back(i);backtrack(path, turnedOn, i+1);path.pop_back();}}

整体代码如下所示：

class Solution {public:unordered_map<int,int> hash={{0,1},{1,2},{2,4},{3,8},{4,1},{5,2},{6,4},{7,8},{8,16},{9,32}};vector<string> res;vector<string> readBinaryWatch(int turnedOn) {vector<int> path;backtrack(path, turnedOn, 0);return res;}void backtrack(vector<int> &path, int turnedOn, int index){if(path.size() == turnedOn){string tmp_res = get_time(path);if(tmp_res.size() > 0){res.push_back(tmp_res);}return;}for(int i=index; i<10; ++i){path.push_back(i);backtrack(path, turnedOn, i+1);path.pop_back();}}string get_time(vector<int> path){pair<int,int> time(0,0); // 初始化时间for(int i : path){if(i<4) time.first+=hash[i];else time.second+=hash[i];}if(time.first>11||time.second>59)//判断合法性return "";string hour = to_string(time.first);string minute = to_string(time.second);if(minute.size() == 1) minute.insert(0, "0");return hour+":"+minute;}};

基于回溯框架求解之分割回文串

回溯问题的大框架就是递归树的展开，只要递归树能够展开回溯问题基本上就求解了一大半了。加上终止条件和剪枝这道题目也就完成得差不多了。我们首先回顾一下上述之前说的几个问题递归树都是如何展开的：

全排列问题：对于给定的一个数组，要求求其全排列，那么对于数组中的每个元素都是这颗递归树上展开的路径上的值，路径上的值添加到path中即可完成递归树的全展开。并且节点的顺序不同也是一种不同的排列，但是元素不能重复访问，因此每次for循环都是从i=0开始的。子集问题：对于给定的一个数组，要求求其所有的子集，同样数组中的每个元素都是这颗递归树上的展开节点，但是与全排列问题不同的地方在于，节点的访问顺序不同是相同的子集，也就是说一旦某个元素被选中了，那么它之后就不能被访问了。对于二进制手表问题：也是相当于要从一个数组中选出n个元素，一旦元素被选定之后，就不能再次选中它了，因此i也是从index开始的。

对于这个分割回文串，也是被玩出花来了，我们可以看一下这道题目：131. 分割回文串：给你一个字符串s，请你将s分割成一些子串，使每个子串都是回文串。返回s所有可能的分割方案。回文串是正着读和反着读都一样的字符串。示例1：

输入：s = "aab"输出：[["a","a","b"],["aa","b"]]

很明显，回溯如果要做的话，首先就是这个递归树怎么建立。首先想一些取过的字符还能再次被取到吗，如果不行的话那么for循环的i就要从index开始，对于这道题，我们是需要每次从index开始的。但是，如果像之前那样，路径上的值每次都取一个的话，肯定是不行的，因此每次应该是取一个子串。那for循环从i=index到s.size()，那么子串也可以从s的index下标到i的下标依次遍历去取，此时回溯算法的主逻辑可以写成：

void backtrack(string &s, vector<string> &path, int index){for(int i=index; i<s.size(); ++i){path.push_back(s.substr(index, i-index+1));backtrack(s, path, i+1);path.pop_back();}}

加上但index访问到s的末端，也就是index==s.size()的时候，递归树就走到了叶子节点，这个时候就需要考虑是否将path的值加入到最终的结果中去了，如果path中的所有元素都是回文子串的话，我们就可以将path中的结果加入到最终的返回数组结果中去了。我们当然可以在将path添加到最终的res结果数组中去之前循环判断path中的元素是否是回文字符串，我们也可以在字符串添加进path数组中的时候就判断这个字符串是否是回文字符串，顺手还可以剪枝一手，一举两得。此时的回溯算法可以写成：

void backtrack(string &s, vector<string> &path, int index){if(s.size() == index){res.push_back(path);}for(int i=index; i<s.size(); ++i){if(!is_HuiWen(s, index, i)){continue;}path.push_back(s.substr(index, i-index+1));backtrack(s, path, i+1);path.pop_back();}}

而判断字符串是否是回文字符串的话，这里传入的是引用，计算开销要小一点，判断字符串是否是回文字符串的函数如下：

bool is_HuiWen(string &s, int left, int right){while(left < right){if(s[left] != s[right]){return false;}++left;--right;}return true;}

到此算法框架就完成了，整体代码如下：

class Solution {public:vector<vector<string>> res;vector<vector<string>> partition(string s) {vector<string> path;backtrack(s, path, 0);return res;}void backtrack(string &s, vector<string> &path, int index){if(s.size() == index){res.push_back(path);}for(int i=index; i<s.size(); ++i){if(!is_HuiWen(s, index, i)){continue;}path.push_back(s.substr(index, i-index+1));backtrack(s, path, i+1);path.pop_back();}}bool is_HuiWen(string &s, int left, int right){while(left < right){if(s[left] != s[right]){return false;}++left;--right;}return true;}};

基于回溯框架求解之八皇后

上述的题目都是在一维的角度求解回溯问题，比如像一个数组，一个字符串这样去展开递归树，但是有一些题目是二维的，需要我们进行二维的递归树展开。比如像Leetcode面试题 08.12. 八皇后问题，说的是：设计一种算法，打印N皇后在N × N棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。示例:

输入：4输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]解释: 4 皇后问题存在如下两个不同的解法。[[".Q..", // 解法 1"...Q","Q...","..Q."],["..Q.", // 解法 2"Q...","...Q",".Q.."]]

每一行每一列都只能放一个，按照习惯，我们假设一行放一个，这样的话我们就需要对列进行遍历，然后每行依次递增，此时的递归树的全展开代码如下所示：

void backtrack(vector<string>& s, int index, int n){// index表示行for(int column=0; column<n; ++column){s[index][column] ='Q';backtrack(s, index+1, n);s[index][column] = '.';}}

按照上述这个全展开，每一行的每个位置都会被放置一个'Q'的全部结果都会遍历得到，这棵树我们是展开了，接下来就是剪枝了。但是在剪枝之前，我们可以先写一首终止条件，也就是将计算得到的某个结果添加到最终的结果中去。终止条件就是当行遍历到最后一行的时候：

void backtrack(vector<string>& s, int index, int n){if(index == n){res.push_back(s);return;}for(int column=0; column<n; ++column){s[index][column] ='Q';backtrack(s, index+1, n);s[index][column] = '.';}}

接下来我们就只需要处理剪枝即可，依据题意，每一行每一列都只能有一个Q，因为我们遍历的时候就是按照行来遍历的，那么对于每一列，我们要保证它不能与其它列重合，那这不就可以用一个集合来记录哪一列被选中了，此时如果当前列在集合中的话，就剪枝去掉即可。这样列的剪枝就可以实现了：

unordered_set<int> set_column;void backtrack(vector<string>& s, int index, int n){if(index == n){res.push_back(s);return;}for(int column=0; column<n; ++column){if(set_column.count(column)){// 第一重剪枝continue;}set_column.insert(column);s[index][column] ='Q';backtrack(s, index+1, n);s[index][column] = '.';set_column.erase(column);}}

还有一个就是斜对角的，因为我们是从上往下依次每行放Q的，所以我们只需要检查左上角，还有右上角上是不是有Q，有的话，我们也需要去剪枝，我们写一个函数，输入当前的棋盘s和当前的row和column，还有判断棋盘边界必须的棋盘长度n：

bool Have_Q(vector<string>& s, int row, int column, int n){for(int i=row-1, j=column-1; i>=0 && j>=0; --i, --j){if(s[i][j] == 'Q') return true;}for(int i=row-1, j=column+1; i>=0 && j<n; --i, ++j){if(s[i][j] == 'Q') return true;}return false;}

之后我们就可以设置第二层剪枝了：

void backtrack(vector<string>& s, int index, int n){if(index == n){res.push_back(s);return;}for(int column=0; column<n; ++column){if(set_column.count(column)){// 第一层剪枝continue;}if(Have_Q(s, index, column, n)){// 第二层剪枝continue;}set_column.insert(column);s[index][column] ='Q';backtrack(s, index+1, n);s[index][column] = '.';set_column.erase(column);}}

到此，回溯算法的主逻辑就写完了，全部代码如下所示：

class Solution {public:vector<vector<string>> res;unordered_set<int> set_column;vector<vector<string>> solveNQueens(int n) {vector<string> s(n, string(n, '.'));backtrack(s, 0, n);return res;}void backtrack(vector<string>& s, int index, int n){// index表示行if(index == n){res.push_back(s);return;}for(int column=0; column<n; ++column){if(set_column.count(column)){// 第一层剪枝continue;}if(Have_Q(s, index, column, n)){// 第二层剪枝continue;}set_column.insert(column);s[index][column] ='Q';backtrack(s, index+1, n);s[index][column] = '.';set_column.erase(column);}}bool Have_Q(vector<string>& s, int row, int column, int n){for(int i=row-1, j=column-1; i>=0 && j>=0; --i, --j){if(s[i][j] == 'Q') return true;}for(int i=row-1, j=column+1; i>=0 && j<n; --i, ++j){if(s[i][j] == 'Q') return true;}return false;}};

基于回溯框架求解之单词搜索

花，花里胡哨的回溯框架的题目它，它又来了。LeetCode 79. 单词搜索：给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中，返回true；否则，返回false。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"输出：true

还是那句话，只要全展开递归树能够全展开，这类题目其实就已经做了一大半了。说白了其实就是在网格里面搜一条路径，那么对于每个网格的位置上面，能够选择的方向只有四个，因此我们可以对这四个方向进行for循环遍历，然后把这颗递归树展开：

vector<pair<int, int>> direction{{0,1}, {0,-1}, {1, 0}, {-1, 0}};void backtrack(vector<vector<char>>& board, vector<vector<int>>& vis, string& word, int row, int column, int index){for(pair<int, int>dir : direction){row = row + dir.first;column = column + dir.second;backtrack(board, vis, word, row, column, index+1);row = row - dir.first;column = column - dir.second;}}

上述代码中，我们把方向放在一个vector数组里面，里面存的是一个pair<int, int>数组。之后还有一个终止条件，还有剪枝需要去处理，我们先来处理一下终止条件，就是当index访问到了最后一个word的长度嘛，那就是对word中的每个字符都检查了一遍。

void backtrack(vector<vector<char>>& board, vector<vector<int>>& vis, string& word, int row, int column, int index){if(index == word.size()){// 终止条件满足，返回结果res = true; return;}for(pair<int, int>dir : direction){row = row + dir.first;column = column + dir.second;backtrack(board, vis, word, row, column, index+1);row = row - dir.first;column = column - dir.second;}}

剩下的一件事情就是剪枝了，首先就是访问的边界条件，如果越界，我们是需要剪枝的，如果访问到了之前已经访问过的元素，我们也是需要去剪枝的，字符不相等的时候我们也是需要去剪枝的。所以我们需要一个二维数组去记录哪些元素已经被访问过了。然后还需要去写一个剪枝的函数：

void backtrack(vector<vector<char>>& board, vector<vector<int>>& vis, string& word, int row, int column, int index){if(index == word.size()){// 终止条件满足，返回结果res = true; return;}for(pair<int, int>dir : direction){if(Purning(board, vis, word, row, column, index)) continue; // 剪枝vis[row][column] = 1;row = row + dir.first;column = column + dir.second;backtrack(board, vis, word, row, column, index+1);row = row - dir.first;column = column - dir.second;vis[row][column] = 0;}}bool Purning(vector<vector<char>>& board, vector<vector<int>>& vis, string& word, int row, int column, int index){if(row < 0 || row >= board.size() || column < 0 || column >= board[0].size()) return true; // 边界情况剪枝。if(board[row][column] == word[index] && !vis[row][column]) return false; // 值不相等情况，和已访问过该节点情况，剪枝。else return true;}

到此整颗递归搜索树就构建完毕了。但是这道题目还有一个骚操作，就是这个递归树展开的根节点是会变动的，也就是说矩阵中的元素与word单词第一个字符相等的时候我们才需要去递归展开这颗递归树，因此我们可以得到完整代码如下所示：

class Solution {public:bool res = false;vector<pair<int, int>> direction{{0,1}, {0,-1}, {1, 0}, {-1, 0}};bool exist(vector<vector<char>>& board, string word) {vector<vector<int>> vis(board.size(), vector<int>(board[0].size()));for(int i=0; i<board.size(); ++i){for(int j=0; j<board[0].size(); ++j){if(board[i][j] == word[0]){backtrack(board, vis, word, i, j, 0);if(res) return res;}}}return res;}void backtrack(vector<vector<char>>& board, vector<vector<int>>& vis, string& word, int row, int column, int index){if(index == word.size()){// 终止条件满足，返回结果res = true; return;}for(pair<int, int>dir : direction){if(Purning(board, vis, word, row, column, index)) continue; // 剪枝vis[row][column] = 1;row = row + dir.first;column = column + dir.second;backtrack(board, vis, word, row, column, index+1);row = row - dir.first;column = column - dir.second;vis[row][column] = 0;}}bool Purning(vector<vector<char>>& board, vector<vector<int>>& vis, string& word, int row, int column, int index){if(row < 0 || row >= board.size() || column < 0 || column >= board[0].size()) return true; // 边界情况剪枝。if(board[row][column] == word[index] && !vis[row][column]) return false; // 值不相等情况，和已访问过该节点情况，剪枝。else return true;}};

基于回溯框架求解之解数独

等等，还没完，回溯算法还有更骚的题，但是万变不离其宗，我们来看一下LeetCode 37. 解数独，编写一个程序，通过填充空格来解决数独问题。数独的解法需遵循如下规则：数字1-9在每一行只能出现一次。数字1-9在每一列只能出现一次。数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）数独部分空格内已填入了数字，空白格用 ‘.’ 表示。示例：

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

这道题目与之前的几道不一样的地方在于它还有一些骚操作，如果想要全展开，不仅要对这个二维矩阵进行遍历，并且在每个小格子上面还需要对数字1-9进行遍历，并且与之前的回溯算法不一样的地方在于，如果这里找到了一个可行解的话，我们就需要返回了，不然会被回溯回去，就相当于什么都没做了。因此我们将回溯函数backtrack()的返回值类型不再设置为void类型，而是将其设置为bool类型，此时全展开的代码可以写成如下形式：

bool backtrack(vector<vector<char>>& board, int index){if(index == 9*9) return true;int row = index / 9;int column = index % 9;for(int i=1; i<=9; ++i){// 每个方格上遍历放九个数字board[row][column] = i+'0';if(backtrack(board, index+1)) return true;board[row][column] = '.';}return false;}

上述代码中已经加入了终止条件，我们只需要再加入剪枝即可，这里的剪枝分为两种情况，如果被选中的小方格中有元素的话，我们就跳过，返回下一个元素的求解结果：

if(board[row][column] != '.'){// 给定行和列上已经有数字后，进行剪枝return backtrack(board, index+1);}

如果是给定的1-9中某个数字不合适的话，我们就continue换掉这个数字，可以写一个剪枝函数来实现这个事情：

bool Pruning(vector<vector<char>>& board, int row, int column, char str_i){for(int i=0; i<9; ++i){if(board[row][i] == str_i) return true; // 对列遍历，剪枝if(board[i][column] == str_i) return true; // 对行遍历，剪枝}int row_new = (row/3)*3, column_new = (column/3)*3; // 对小的九宫格进行遍历for(int i=row_new; i<row_new+3; ++i){for(int j=column_new; j<column_new+3; ++j){if(board[i][j] == str_i) return true;}}return false;}

所有的代码如下所示：

class Solution {public:void solveSudoku(vector<vector<char>>& board) {backtrack(board, 0);}bool backtrack(vector<vector<char>>& board, int index){if(index == 9*9) return true;int row = index / 9;int column = index % 9;for(int i=1; i<=9; ++i){// 每个方格上遍历放九个数字if(board[row][column] != '.'){// 给定行和列上已经有数字后，进行剪枝，这一剪枝条件放到for循环外面也是可以的return backtrack(board, index+1);}if(Pruning(board, row, column, i+'0')){continue;}board[row][column] = i+'0';if(backtrack(board, index+1)) return true;board[row][column] = '.';}return false;}bool Pruning(vector<vector<char>>& board, int row, int column, char str_i){//if(board[row][column] != '.') return true;for(int i=0; i<9; ++i){if(board[row][i] == str_i) return true; // 对列遍历，剪枝if(board[i][column] == str_i) return true; // 对行遍历，剪枝}int row_new = (row/3)*3, column_new = (column/3)*3; // 对小的九宫格进行遍历for(int i=row_new; i<row_new+3; ++i){for(int j=column_new; j<column_new+3; ++j){if(board[i][j] == str_i) return true;}}return false;}};