回溯大法总结

前言

本篇博客将分两步来进行，首先谈谈我对回溯法的理解，然后通过若干道题来进行讲解，最后总结

对回溯法的理解

回溯法可以看做蛮力法的升级版，它在解决问题时的每一步都尝试所有可能的选项，最终找出所以可行的方案。回溯法非常适合解决由多个步骤组成的问题，并且每个步骤都有多个选项，在每一步选择了其中一个选项之后，就进入下一步，然后又会面临新的选项，就这样重复选择，直至最终的状态。

用回溯法解决问题的过程可以形象地用一个树形结构表示，求解问题的每个步骤可以看作树中的一个节点。如果在某一步有n个可能的选项，每个选项是树中的一条边，经过这些边就可以到达该节点的个子节点。

在采用回溯法解决问题时如果到达树形结构的叶节点，就找到了问题的一个解。如果希望找到更多的解，那么还可以回溯到它的父节点再次尝试父节点其它的选项。如果父节点所有可能的选项都已经试过，那么再回溯到父节点的父节点以尝试它的其他选项，这样逐层回溯到树的根节点。因此，采用回溯法解决问题的过程实质上是在树形结构中从根节点开始进行深度优先遍历。通常，回溯法的深度优先遍历用递归代码实现。

由于回溯法是在所有选项形成的树上进行深度优先遍历，如果解决问题的步骤比较多或每个步骤都面临多个选项，那么遍历整棵树将需要较多的时间，如果明确知道某些子树没有必要遍历，那么在遍历的时候应该避开这些子树以优化效率。通常将使用回溯法时避免遍历不必要的子树的方法称为剪枝。

用回溯解决集合的组合，排列问题

组合不看重元素顺序，因此两个集合中元素个数相同，各元素个数相同，这两个集合就是一个组合。

排列看重元素顺序，因此两个集合中元素个数相同，各元素个数相同，但是元素顺序不同的话，这两个集合就是两个不同的排列。

所有子集

题目

分析

以集合【1,2】为例，有两个元素，每个元素都面临选和不选两种选择，树形图如下图所示：

本题中生成一个子集，可分为若干步，并且每一步都面临若干选择，这正是采用回溯法的典型场景。

代码

class Solution {
public:vector<vector<int>> vv;vector<int> v;vector<int> cnums;vector<vector<int>> subsets(vector<int>& nums) {cnums=nums;dfs(0);return vv;}void dfs(int pos){if(pos==cnums.size()){vv.push_back(v);return;}dfs(pos+1);v.push_back(cnums[pos]);dfs(pos+1);v.pop_back();}
};

在回溯到父节点时，清除之前相应的修改，即恢复现场。

包含K个元素的组合

题目

分析

集合的一个组合也是一个子集，因此求集合的组合的过程和求子集的过程是一样的，这个题目较钱一道题只是增加了一个限制条件，即只找出包含K个数字的组合，只需要在前一道题的基础上稍加修改即可，就可以找出所有包含K个数字的组合。

代码

class Solution {
public:vector<vector<int>> vv;vector<int> v;vector<vector<int>> combine(int n, int k) {dfs(n,k,1);return vv;}void dfs(int n,int k,int pos){if(v.size()==k){vv.push_back(v);return;}if(pos<=n){dfs(n,k,pos+1);v.push_back(pos);dfs(n,k,pos+1);v.pop_back();}}
};

允许重复选择元素的组合

题目

分析

这个题目仍然是关于组合的，但组合中的一个数字可以出现任意次，可以以不变应万变，用回溯法来解决这个问题。

能够用回溯法解决的问题都能够分成若干步来解决，每一步都面临若干选择。对于从集合中选取数字组成组合的问题而言，集合中有多少个数字，解决这个问题就需要多少步，每一步都从集合中取出一个下标为i的数字，此时面临两个选择。一个选择是跳过这个数字不将该数字添加到组合中，那么这一步实际上什么都不做，接下来处理下标为i+1的数字。另一个选择是将该数字添加到组合中，由于一个数字可以重复在集合中出现，也就是说，下一步可能再次选择同一个数字，因此下一步仍然处理下标为i的数字。

代码

class Solution {
public:vector<vector<int>> vv;vector<int> v;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {helper(candidates,target,0);return vv;}void helper(vector<int>& candidates, int target,int pos){if(target==0){vv.push_back(v);return;}else if(pos<candidates.size() && target>0){helper(candidates,target,pos+1);v.push_back(candidates[pos]);helper(candidates,target-candidates[pos],pos);v.pop_back();}}
};

应用回溯法解决问题时如果有可能应尽可能剪枝以优化时间效率。由于题目明确指出数组中的所有数字都是正整数，因此当组合中已有数字之和已经大于目标值时（即递归函数helper的参数target的值小于0时）就没必要再考虑数组中还没有处理的数字，因为再在组合中添加任意正整数元素之后和会更大，一定找不到新的符合条件的组合，也就没必要再继续尝试，这就是函数helper中else if的条件中补充了一个target大于0的判断条件的原因。

包含重复元素集合的组合

题目

分析

这个题目和之前几个题目与组合相关的题目相比，最大的不同之处在于输入的集合中有重复的数字但输出不得包含重复的组合，如果输入的集合中有重复的数字，不经过特殊处理将产生重复的集合。

避免重复的组合的方法就是当在某一步决定跳过某个值为m的数字时，跳过所有值为m的数字。

为了方便跳过后面所有值相同的数字，可以将集合中的数字排序，将相同的数字放在一起，这样方便比较数字。当决定跳过某个值的数字时，可以按顺序扫描后面的数字，直到找到不同的只为止。

代码

class Solution {
public:vector<vector<int>> vv;vector<int> v;vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());helper(candidates,target,0);return vv;}void helper(vector<int>& candidates, int target,int pos){if(target==0){vv.push_back(v);return;}else if(pos<candidates.size() && target>0){int next=pos;while(next<candidates.size() && candidates[next]==candidates[pos]) next++;helper(candidates,target,next);v.push_back(candidates[pos]);helper(candidates,target-candidates[pos],pos+1);v.pop_back();}}
};

没有重复元素集合的全排列

题目

分析

假设集合有n个元素，那么生成一个全排列需要n步，当生成排列的第一个数字时会面临n个选项，即n个数字都有可能成为排列的第1个数字，生成排列的第二个数字会面临n-1个选项，即剩下的n-1个数字都有可能成为排列的第2个数字，以此类推。看起来解决这个问题可以分为n步，每一步都面临若干选项，这就是典型的适用回溯法的场景。

方法一

使用一个bool类型数组来标记是否被访问过，每次填写排列的第I个位置时，都从前往后一次遍历没有被访问过的数字，加入排列。

class Solution {
public:vector<vector<int>> vv;vector<int> v;vector<int> cpnums;bool vis[10];vector<vector<int>> permute(vector<int>& nums) {cpnums=nums;helper(0);return vv;}void helper(int pos){if(pos==cpnums.size()){vv.push_back(v);return;}for(int i=0;i<cpnums.size();i++){if(!vis[i]){v.push_back(cpnums[i]);vis[i]=true;helper(pos+1);vis[i]=false;v.pop_back();}}}
};

方法二

排列和组合不同，排列与元素顺序相关，交换数字能够得到不同的排列，生成全排列的过程，就是交换输入集合中元素的顺序以得到不同的排列。

class Solution {
public:vector<vector<int>> vv;vector<int> cpnums;int n;vector<vector<int>> permute(vector<int>& nums) {cpnums=nums;n=cpnums.size();helper(0);return vv;}void helper(int pos){if(pos==n){vector<int> v;for(int x:cpnums)v.push_back(x);vv.push_back(v);}else{for(int i=pos;i<n;i++){Swap(&cpnums[pos],&cpnums[i]);helper(pos+1);Swap(&cpnums[pos],&cpnums[i]);}}}void Swap(int* a,int* b){int tmp=*a;*a=*b;*b=tmp;}
};

包含重复元素集合的全排列

题目

分析

如果集合中有重复的数字，那么交换集合中重复的数字得到的全排列是同一个全排列，例如交换[1,1,2]中的两个数字1并不能得到新的全排列。

为了便于解决有重复元素会出现相同排列问题，先将数组的元素进行排序。

方法一

易知，以红色区域为根节点的子树应该剪掉，但是以绿色区域为根节点的子树是正确的，那么怎么区分二者那？

通过观察不难发现，绿色区域中，目前已填的元素a与前一个元素相同，且前一个元素已经被访问过了，但是红色区域中，目前已填的元素与前一个元素相同，但是前一个元素没有被访问过，这个点就是突破口。

以nums为例，判断条件为  i>0 && nums[i]=nums[i-1] && !vis[i-1]  。

class Solution {
public:vector<vector<int>> vv;vector<int> v;vector<int> cpnums;bool vis[10]={false};int n;vector<vector<int>> permuteUnique(vector<int>& nums) {cpnums=nums;n=cpnums.size();sort(cpnums.begin(),cpnums.end());helper(0);return vv;}void helper(int pos){if(pos==n){vv.push_back(v);return;}for(int i=0;i<n;i++){if(!vis[i]){if(i>0 && cpnums[i]==cpnums[i-1] && !vis[i-1]) continue;v.push_back(cpnums[i]);vis[i]=true;helper(pos+1);vis[i]=false;v.pop_back();}}}
};

方法二

class Solution {
public:vector<vector<int>> vv;int n;vector<int> cpnums;bool vis[10];vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());cpnums=nums;n=cpnums.size();helper(0);return vv;}void helper(int pos){if(pos==n){vector<int> v;for(int x:cpnums)v.push_back(x);vv.push_back(v);return;}else{set<int> st;for(int i=pos;i<n;i++){if(!st.count(cpnums[i])){st.emplace(cpnums[i]);Swap(&cpnums[pos],&cpnums[i]);helper(pos+1);Swap(&cpnums[pos],&cpnums[i]);}}}}void Swap(int* a,int* b){int tmp=*a;*a=*b;*b=tmp;}
};

该方法不同于方法一，除了是通过交换不同位置的元素之外，在解决重复元素会出现相同全排列问题上，使用set将已访问的元素进行统计，当与要访问的元素相等的元素已经被访问过，那么访问该元素没问题，但是与要访问的元素相等的元素没有被访问过，那么就会出现相同的全排列，因此这一点就是突破口，其实思想还是和方法一解决的突破点一样。

用回溯法解决其它类型的问题

生成匹配的括号

题目

分析

如果输入n,那么生成的括号组合包含n个左括号和n个右括号。因此生成这样的组合需要2n步，每一步生成一个括号，每一步都面临两个选项，既可能生成左括号又可能生成右括号。由此看来，这个问题很适合用回溯法解决。

在生成括号组合时需要注意每一步都要满足限制条件。第一个限制条件是左括号或右括号的树木不能唱过n个。第二个限制条件是括号的匹配原则，即在任意步骤中已经生成的右括号的数目不能唱过左括号的数目。

代码

class Solution {
public:vector<string> v;string s;vector<string> generateParenthesis(int n) {helper(n,n);return v;}void helper(int left,int right){if(left==0 && right==0){v.push_back(s);return;}if(left>0){s+='(';helper(left-1,right);s.pop_back();}if(right>left){s+=')';helper(left,right-1);s.pop_back();}}
};

分割回文子字符串

题目

分析

当处理到字符创中的某个字符时，如果包括该字符在内后面还有n个字符，那么此时面临n个选项，即分割出长度为1的子字符串（只包含该字符），分割出长度为2的子字符串，以此类推，分割出长度为n的子字符串由于题目要求分割出来的每个子字符串都是回文的，因此需要逐一判断这n个子字符串是不是回文的，只有回文子字符串才是符合条件的分割，分割出一段回文子字符串之后，接着分割后面的字符串。

代码

class Solution {
public:vector<vector<string>> ans;vector<string> v;string cps;int n;vector<vector<string>> partition(string s) {cps=s;n=cps.size();helper(0);return ans;}void helper(int start){if(start==n){ans.push_back(v);return;}for(int i=start;i<n;i++){if(isPalindrome(start,i)){v.push_back(cps.substr(start,i-start+1));helper(i+1);v.pop_back();}}}bool isPalindrome(int begin,int end){while(begin<end){if(cps[begin++]!=cps[end--])return false;}return true;}
};

恢复IP地址

题目

分析

IP地址的特点：一个IP被3个 '.' 字符分割成4段，每段都是从0到255之间的一个数字，另外，除“0”本身外，其他数字不能以‘0’开头。

如果输入的字符串长度为n，由于逐一处理字符串中的每个字符，因此需要n步，并且每一步都面临两个可能的选项，由此可见，适合用回溯法来解决。

代码

class Solution {
public:bool isValidSeg(string seg){return (stoi(seg) <=255) && (seg == "0" || seg[0] !='0');}void helper(string s,int i,int segI,string seg,string ip,vector<string>& result){if(i==s.length() && segI == 3 && isValidSeg(seg))result.push_back(ip+seg);else if(i<s.length() && segI <=3){char ch=s[i];if(isValidSeg(seg+ch))helper(s,i+1,segI,seg+ch,ip,result);if(seg.length()>0 && segI<3)helper(s,i+1,segI+1,string(1,ch),ip+seg+".",result);}}vector<string> restoreIpAddresses(string s) {vector<string> result;helper(s,0,0,"","",result);return result;}
};

总结

如果解决一个问题需要若干步骤，并且在每一步都面临若干选项，那么可以尝试用回溯法解决这个问题。适合用回溯法解决的问题的一个特点是解决这个问题存在多个解，而题目往往要求列出所有的解。

采用回溯法能够解决集合的排列，组合的很多问题，仔细分析这些问题及变种的代码就会发现最终的代码都大同小异，都可以采用递归来实现。递归代码需要先确定递归退出的边界条件，然后逐个处理集合中的元素。对于组合类问题，每个数字都面临两个选项，即添加当前数字到组合中或不添加当前数字到组合中。对于排列问题，一个数字如果后面有n个数字，那么面临n+1个选择，即可以将该数字和它后面的数字（包括它本身）交换。根据这些选项做出选择之后再调用递归函数处理后面的数字。