基于回溯框架求解之子集
上文说的是将整棵递归树全部展开，然后找到剪枝条件进行剪枝。但是有一类问题就不是很适合用递归树的全展开，比如像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"); // 判断分钟前面是否要加个0 return 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; } };
