算法题总结（十二）——回溯算法（上）

回溯算法

所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数。

虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。

因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

回溯是递归的副产品，只要有递归就会有回溯

回溯法就是暴力搜索，并不是什么高效的算法，最多再剪枝一下。

如果我们需要穷举的时候，就可以使用遍历加递归！

回溯法解决的问题

回溯法，一般可以解决如下几种问题：

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

回溯法抽象为树形结构后，其遍历过程就是：for循环横向遍历，递归纵向遍历，回溯不断调整结果集

大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，回溯不断调整结果集，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

回溯算法模板

void backtracking(参数) {
if (终止条件) {存放结果;return;
}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果
}
}

组合问题

77、组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

上面我们说了要解决 n为100，k为50的情况，暴力写法需要嵌套50层for循环，那么回溯法就用递归来解决嵌套层数的问题。

递归来做层叠嵌套（可以理解是开k层for循环），每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了。

然后还需要一个参数，为int型变量startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历，startIndex 就是防止出现重复的组合。

剪枝：

所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了。

在for循环上做剪枝操作是回溯法剪枝的常见套路！ 后面的题目还会经常用到。

接下来看一下优化过程如下：

已经选择的元素个数：path.size();
还需要的元素个数为: k - path.size();
在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。

举个例子，n = 4，k = 3，目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

从2开始搜索都是合理的，可以是组合[2, 3, 4]。

这里大家想不懂的话，建议也举一个例子，就知道是不是要+1了。

class Solution {List<List<Integer>> result =new ArrayList<>();List<Integer> path =new ArrayList<>();public List<List<Integer>> combine(int n, int k) {backtrack(n,k,1);return result;}private void backtrack(int n,int k,int startIndex){if(path.size()==k){result.add(new ArrayList(path));  //这里一定要新建一个return;}for(int i=startIndex;i<=n-(k-path.size())+1;i++)  //剪枝，不剪枝的话就是i<=n{path.add(i);backtrack(n,k,i+1);path.remove(path.size()-1);}}
}

216、组合总和三

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

此题和上面的一样，只不过加了一个总和的限制。整体思路还是一样的，本题的剪枝会好想一些，即：已选元素总和如果已经大于n（题中要求的和）了，那么往后遍历就没有意义了，直接剪掉。在本题中，依然还可以有一个剪枝，就是上题中提到的，对for循环选择的起始范围的剪枝。

此题和上面一样，只不过可取的数字范围是1-9

数量+总和限制

class Solution {List<List<Integer>> result =new ArrayList<>();LinkedList<Integer> path =new LinkedList<>();private int getsum(){int sum=0;  //局部变量赋初值for(int i=0;i<path.size();i++){sum += path.get(i);}return sum;}private void backtrack(int k,int n,int index){if(getsum()>n) return;  //剪枝,和大于n，需要剪枝if(path.size()==k && getsum()==n){result.add(new LinkedList<>(path));return;}//当后面个数不足我们需要的个数时，也需要剪枝for(int i=index;i<=9-(k-path.size())+1;i++){path.add(i);backtrack(k,n,i+1);path.removeLast();}}public List<List<Integer>> combinationSum3(int k, int n) {backtrack(k,n,1);return result;}
}

17、电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

本题是属于不同的集合中的组合，用一个字符数组表示不同字母代表的集合，然后用一个index表示digits中的第几个字母。用StringBuilder来表示path路径。

结果集中是字符串的时候，使用sb来作为路径path。

注意这里的index不是之前组合中的index，这个index是为了选取不同的集合。

class Solution {List<String> result =new ArrayList<>();StringBuilder path=new StringBuilder();String[] strings ={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};public List<String> letterCombinations(String digits) {if(digits==null || digits.length()==0)return result;backtrack(digits,0);  //先从digits中的第0个字母开始return result;}  private void backtrack(String digits,int index){//index表示digits中的第几个字母，从而选不同的集合//因为index每次是加1，所以当index与digits的长度相同时，说明得到了想要的结果if(index==digits.length()){result.add(new String(path));  //或者path.toString()return;}//选取要遍历的集合String string = strings[digits.charAt(index)-'0'];//遍历集合for(int i=0;i<string.length();i++){path.append(string.charAt(i));backtrack(digits,index+1);path.deleteCharAt(path.length()-1);}}}

39、组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

本题相比较于上面的组合题目，有两点不同：

组合没有数量要求
元素可无限重复选取，但是有总和要求，所以还是总数还是被限制。

本题还需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？

我举过例子，如果是一个集合来求组合的话，就需要startIndex，例如：77.组合 (opens new window)，216.组合总和III (opens new window)。

如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合

注意以上我只是说求组合的情况，如果是排列问题，又是另一套分析的套路，后面我在讲解排列的时候会重点介绍。

所以，一个集合中的组合问题，是需要使用startIndex的。因为组合不和排列一样，组合是没有顺序的！

对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历，因为如果不排序的话，可能还会有更小的元素。

求和问题：排序+剪枝

class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path =new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backtrack(candidates,target,0);return result;}private void backtrack(int[] candidates,int target,int index){if(getsum()>target)  //剪枝return;if(getsum()==target){result.add(new ArrayList(path));return;}for(int i=index;i<candidates.length;i++)  //此处没有k的限制{path.add(i);//因为可以重复，所以这里还是从i开始backtrack(candidates,target,i);path.remove(path.size()-1);}}private int getsum(){int sum=0;for(int i=0;i<path.size();i++){sum+=path.get(i);}return sum;}
}

上面的代码会超时！

因为即使排序之后，使用getsum()>target来剪枝的话，在for循环中，依然要进行到下一层的递归，而且for循环要执行结束，所以增加了复杂度！因为如果是大于target，后面也没有必要搜索了！

在求和问题中，排序之后加剪枝是常见的套路！

以及上面的版本一的代码大家可以看到，对于sum已经大于target的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断sum > target的话就返回。

其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。

那么可以在for循环的搜索范围上做做文章了。

上面不排序的话，会超时，所以排序后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。

在求和问题中，排序之后加剪枝是常见的套路！

class Solution {List<List<Integer>> result =new ArrayList<>();LinkedList<Integer> path =new LinkedList<>();private int getsum(){   int sum=0;for(int i=0;i<path.size();i++){sum+=path.get(i);}return sum;}private void backtrack(int[]candidates,int target,int index)  //index为开始点，因为从头开始结果会重复{if(getsum()==target){result.add(new ArrayList(path));return;}for(int i=index;i<candidates.length;i++){if(getsum()+candidates[i]>target)  //后面也没有必要搜索了break;  //剪枝path.add(candidates[i]);backtrack(candidates,target,i);  //因为元素可以重复，所以这里还是从i开始path.removeLast();}}public List<List<Integer>> combinationSum(int[] candidates, int target) {//不剪枝的话会超时，所以要先排序，然后剪枝Arrays.sort(candidates);backtrack(candidates,target,0);return result;}
}

40、组合总和二

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

本题属于集合（数组candidates）有重复元素，但还不能有重复的组合，需要排序+去重。

有重复的元素，所以需要去重！

这道题目和39.组合总和 (opens new window)如下区别：

本题candidates 中的每个数字在每个组合中只能使用一次。
本题数组candidates的元素是有重复的，而39.组合总和 (opens new window)是无重复元素的数组candidates.

最后本题和39.组合总和 (opens new window)要求一样，解集不能包含重复的组合。

本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。

一些同学可能想了：我把所有组合求出来，再用set或者map去重，这么做很容易超时！

所以要在搜索的过程中就去掉重复组合。

这个去重为什么很难理解呢，所谓去重，其实就是使用过的元素不能重复选取。 这么一说好像很简单！

都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。

那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？

回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。

所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

强调一下，树层去重的话，需要对数组排序！

即同一个树枝上的元素可以重复，同一层的不可以重复选取。

使用used数组的情况：

我在图中将used的变化用橘黄色标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下：

used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
used[i - 1] == false，说明同一树层candidates[i - 1]使用过

我们可以不用used数组来去重，使用index与i的关系来判断是同一个树枝还是同一层，遍历的过程中，i>index时，就是属于同一层，i==index时，是属于同一个树枝的。

class Solution {List<List<Integer>> result =new ArrayList<>();LinkedList<Integer> path =new LinkedList<>();private int getsum(){int sum=0;for(int i=0 ;i<path.size();i++){sum+=path.get(i);}return sum; }private void backtrack(int[] candidates,int target,int index){if(getsum()==target){result.add(new LinkedList(path));return;}for(int i=index; i<candidates.length ;i++){if(getsum()+candidates[i]>target)   //剪枝，也可以把getsum()+candidates[i]<=target放入到for循环中break;   //剪枝if(i>index && candidates[i]==candidates[i-1]) //if语句后面一定不能多分号{ continue; //去重}path.add(candidates[i]);backtrack(candidates,target,i+1);  //不重复的元素path.removeLast();}}public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);backtrack(candidates,target,0);return result;}
}

使用set来对同一层去重：

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort( candidates );backtracking(candidates,target,0);return result;}private int getsum(){int sum=0;for(int i=0 ;i<path.size();i++){sum+=path.get(i);}return sum; }public void backtracking(int[] candidates,int target,int startIndex){if( getsum()==target ){result.add( new ArrayList<>(path) );return;}HashSet<Integer> hashSet = new HashSet<>();   //同一层使用的是一个hashSetfor( int i = startIndex; i < candidates.length; i++){if(getsum()+candidates[i]>target)   break;   //剪枝if( hashSet.contains(candidates[i]) ){continue;   //去重}hashSet.add(candidates[i]);path.add(candidates[i]);backtracking(candidates,target,i+1);path.removeLast();}}
}

总结：如果求和问题，一定是要有序后，在剪枝。

如果有重复元素，则要进行去重，因为有index，所以去重可以不使用used数组。

切割问题

131、分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

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

示例 2：

输入：s = "a"
输出：[["a"]]

本题这涉及到两个关键问题：

切割问题
判断回文

相信这里不同的切割方式可以搞懵很多同学了。

这种题目，想用for循环暴力解法，可能都不那么容易写出来，所以要换一种暴力的方式，就是回溯。

一些同学可能想不清楚回溯究竟是如何切割字符串呢？

我们来分析一下切割，其实切割问题类似组合问题。

例如对于字符串abcdef：

组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…。
切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…。

感受出来了不？

所以切割问题，也可以抽象为一棵树形结构，如图：

递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。

用回溯实现分割，和组合一样。组合是index开始选取数字i 分割是实现从index到i的后面的分割。

我列出如下几个难点：

切割问题可以抽象为组合问题
如何模拟那些切割线，用for循环遍历时候的i表示，切割线在i的后面
切割问题中递归如何终止，index等于s的长度时
在递归循环中如何截取子串，使用substring（）函数
如何判断回文

class Solution {List<List<String>> result =new ArrayList<>();LinkedList<String> temp=new LinkedList<>();private boolean isPalindrome(String s,int left,int right){   for(int i=left,j=right;i<j;i++,j--){if(s.charAt(i)!=s.charAt(j))return false;}return true;}private void backtrack(String s,int index){if(index=s.length()){result.add(new LinkedList(temp));return;}for(int i=index;i<s.length();i++){if(isPalindrome(s,index,i))  //判断每一层分割后的子串，是否为回文串{temp.add(s.substring(index,i+1));}else{continue;   //如果不是回文串 一定要结束，不用向下递归了，剪枝}backtrack(s,i+1);temp.removeLast();}}//回溯的本质就是多重循环，for循环里套了递归！//用回溯实现分割，和组合一样。组合是index开始选取数字i   分割是实现从index到i的分割//for遍历的是行数即树的每一层，递归是遍历的深度。public List<List<String>> partition(String s) {backtrack(s,0);return result;}
}

93、复原IP地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和“192.168.1.1” 是有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

此题也是属于分割问题：切割问题就可以使用回溯搜索法把所有可能性搜出来

startIndex一定是需要的，因为不能重复分割，记录下一层递归分割的起始位置。

本题我们还需要一个变量pointNum，记录添加逗点的数量。

上一题是分割+判断子串是否回文

这一题是分割+判断子串是否合法

判断子串是否合法

最后就是在写一个判断，来判断子串是否是有效子串了。

主要考虑到如下三点：

段位以0为开头的数字不合法
段位里有非正整数字符不合法
段位如果大于255了不合法

class Solution {List<String> result =new ArrayList<>();public List<String> restoreIpAddresses(String s) {if(s.length()>12) return result; //也相当于剪枝了StringBuilder sb =new StringBuilder(s);  //使用sb处理，效率更高backtrack(sb,0,0);return result;
}//num是逗点的数量
private void backtrack(StringBuilder sb,int index,int num)
{if(num==3) // 逗点数量为3时，分隔结束// 判断第四段⼦字符串是否合法，如果合法就放进result中{if(isValid(sb,index,sb.length()-1)){result.add(sb.toString());  //result.add(new String(sb));}return;}for(int i=index;i<sb.length();i++){if(isValid(sb,index,i))  //从index到i满足要求{sb.insert(i+1,'.');backtrack(sb,i+2,num+1);   //隐含了回溯sb.deleteCharAt(i+1);}else     //如果不满足，后面的for循环也不用继续了,注意和上一题的区别break;}}private boolean isValid(StringBuilder sb,int start,int end)
{if(start>end) return false;if(sb.charAt(start)=='0' && start!=end)return false;int sum=0;for(int i=start;i<=end;i++){int digit= sb.charAt(i)-'0'; sum=sum*10+digit;if(sum>255)return false;}return true;
}
}