回溯算法(backtracking)、
什么是回溯法
回溯法也可以叫做回溯搜索法,它是一种搜索的方式。
在二叉树系列中,我们已经不止一次,提到了回溯,例如二叉树:以为使用了递归,其实还隐藏着回溯 (opens new window)。
回溯是递归的副产品,只要有递归就会有回溯。
所以以下讲解中,回溯函数也就是递归函数,指的都是一个函数。
回溯法的效率
回溯法的性能如何呢,这里要和大家说清楚了,虽然回溯法很难,很不好理解,但是回溯法并不是什么高效的算法。
因为回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案,如果想让回溯法高效一些,可以加一些剪枝的操作,但也改不了回溯法就是穷举的本质。
那么既然回溯法并不高效为什么还要用它呢?
因为没得选,一些问题能暴力搜出来就不错了,撑死了再剪枝一下,还没有更高效的解法。
此时大家应该好奇了,都什么问题,这么牛逼,只能暴力搜索。
回溯法解决的问题
回溯法,一般可以解决如下几种问题:
- 组合问题:N个数里面按一定规则找出k个数的集合
- 切割问题:一个字符串按一定规则有几种切割方式
- 子集问题:一个N个数的集合里有多少符合条件的子集
- 排列问题:N个数按一定规则全排列,有几种排列方式
- 棋盘问题:N皇后,解数独等等
相信大家看着这些之后会发现,每个问题,都不简单!
另外,会有一些同学可能分不清什么是组合,什么是排列?
组合是不强调元素顺序的,排列是强调元素顺序。
例如:{1, 2} 和 {2, 1} 在组合上,就是一个集合,因为不强调顺序,而要是排列的话,{1, 2} 和 {2, 1} 就是两个集合了。
记住组合无序,排列有序,就可以了。
回溯法模板
这里给出Carl总结的回溯算法模板。
在讲二叉树的递归 (opens new window)中我们说了递归三部曲,这里我再给大家列出回溯三部曲。
- 回溯函数模板返回值以及参数
在回溯算法中,我的习惯是函数起名字为backtracking,这个起名大家随意。
回溯算法中函数返回值一般为void。
再来看一下参数,因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来,所以一般是先写逻辑,然后需要什么参数,就填什么参数。
但后面的回溯题目的讲解中,为了方便大家理解,我在一开始就帮大家把参数确定下来。
回溯函数伪代码如下:
function backtracking(参数)
- 回溯函数终止条件
既然是树形结构,那么我们在讲解二叉树的递归 (opens new window)的时候,就知道遍历树形结构一定要有终止条件。
所以回溯也有要终止条件。
什么时候达到了终止条件,树中就可以看出,一般来说搜到叶子节点了,也就找到了满足条件的一条答案,把这个答案存放起来,并结束本层递归。
所以回溯函数终止条件伪代码如下:
if (终止条件) {
存放结果;
return;
}
- 回溯搜索的遍历过程
在上面我们提到了,回溯法一般是在集合中递归搜索,集合的大小构成了树的宽度,递归的深度构成的树的深度。
如图:
注意图中,我特意举例集合大小和孩子的数量是相等的!
回溯函数遍历过程伪代码如下:
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
for循环就是遍历集合区间,可以理解一个节点有多少个孩子,这个for循环就执行多少次。
backtracking这里自己调用自己,实现递归。
大家可以从图中看出for循环可以理解是横向遍历,backtracking(递归)就是纵向遍历,这样就把这棵树全遍历完了,一般来说,搜索叶子节点就是找的其中一个结果了。
分析完过程,回溯算法模板框架如下:
function backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
这份模板很重要,后面做回溯法的题目都靠它了!
leetcode精选
[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]]
解析
那么我把组合问题抽象为如下树形结构:
可以看出这个棵树,一开始集合是 1,2,3,4, 从左向右取数,取过的数,不在重复取。
第一次取1,集合变为2,3,4 ,因为k为2,我们只需要再取一个数就可以了,分别取2,3,4,得到集合[1,2] [1,3] [1,4],以此类推。
每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围。
图中可以发现n相当于树的宽度,k相当于树的深度。
那么如何在这个树上遍历,然后收集到我们要的结果集呢?
图中每次搜索到了叶子节点,我们就找到了一个结果。
相当于只需要把达到叶子节点的结果收集起来,就可以求得 n个数中k个数的组合集合。
回溯法三部曲
- 递归函数的返回值以及参数
在这里要定义两个全局变量,一个用来存放符合条件单一结果,一个用来存放符合条件结果的集合。
代码如下:
let resArr; // 存放符合条件结果的集合
let tempArr; // 用来存放符合条件结果
其实不定义这两个全局变量也是可以的,把这两个变量放进递归函数的参数里,但函数里参数太多影响可读性,所以我定义全局变量了。
函数里一定有两个参数,既然是集合n里面取k的数,那么n和k是两个int型的参数。
然后还需要一个参数,为int型变量startIndex,这个参数用来记录本层递归的中,集合从哪里开始遍历(集合就是[1,...,n] )。
为什么要有这个startIndex呢?
每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围,就是要靠startIndex。
从下图中红线部分可以看出,在集合[1,2,3,4]取1之后,下一层递归,就要在[2,3,4]中取数了,那么下一层递归如何知道从[2,3,4]中取数呢,靠的就是startIndex。
所以需要startIndex来记录下一层递归,搜索的起始位置。
那么整体代码如下:
backTracking(n, k, startIndex, tempArr);
- 回溯函数终止条件
什么时候到达所谓的叶子节点了呢?
path这个数组的大小如果达到k,说明我们找到了一个子集大小为k的组合了,在图中path存的就是根节点到叶子节点的路径。
如图红色部分:
此时用result二维数组,把path保存起来,并终止本层递归。
所以终止条件代码如下:
if (tempArr.length === k) { //终止条件
resArr.push(tempArr.slice());
return;
}
- 单层搜索的过程
回溯法的搜索过程就是一个树型结构的遍历过程,在如下图中,可以看出for循环用来横向遍历,递归的过程是纵向遍历。
如此我们才遍历完图中的这棵树。
for循环每次从startIndex开始遍历,然后用path保存取到的节点i。
代码如下:
for (let i = startIndex; i <= n - k + 1 + tempArr.length; i++) { // 控制树的横向遍历
tempArr.push(i);// 处理节点
backTracking(n, k, i + 1, tempArr);// 递归:控制树的纵向遍历,注意下一层搜索要从i+1开始
tempArr.pop(); //剔除父级 回溯
}
可以看出backtracking(递归函数)通过不断调用自己一直往深处遍历,总会遇到叶子节点,遇到了叶子节点就要返回。
backtracking的下面部分就是回溯的操作了,撤销本次处理的结果。
function combine(n: number, k: number): number[][] {
let resArr: number[][] = [];
function backTracking(n: number, k: number, startIndex: number, tempArr: number[]): void {
if (tempArr.length === k) { //终止条件
resArr.push(tempArr.slice());
return;
}
for (let i = startIndex; i <= n ; i++) { //
tempArr.push(i);
backTracking(n, k, i + 1, tempArr);
tempArr.pop(); //剔除父级
}
}
backTracking(n, k, 1, []);
return resArr;
};
剪枝
图中每一个节点(图中为矩形),就代表本层的一个for循环,那么每一层的for循环从第二个数开始遍历的话,都没有意义,都是无效遍历。
所以,可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了,那么就没有必要搜索了。
注意代码中i,就是for循环里选择的起始位置。
for (let i = startIndex; i <= n; i++) {
接下来看一下优化过程如下:
- 已经选择的元素个数: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了。
所以优化之后的for循环是:
for (let i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置
[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 。
仅有这两种组合。
示例 2:输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3:输入: candidates = [2], target = 1
输出: []
从叶子节点可以清晰看到,终止只有两种情况,sum大于target和sum等于target。
function combinationSum(candidates: number[], target: number): number[][] {
let resArr :number[][] = [];
function backTracking(sum:number,index:number,tempArr:number[]){
if(sum>target){
return
}
if(sum===target) {
resArr.push(tempArr.slice());
return
}
for(let i=index; i<candidates.length; i++){
tempArr.push(candidates[i]);
backTracking(sum+candidates[i],i,tempArr);
tempArr.pop();
}
}
backTracking(0,0,[])
return resArr
};
[46] 全排列
给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2:输入:nums = [0,1]
输出:[[0,1],[1,0]]
示例 3:输入:nums = [1]
输出:[[1]]
function permute(nums: number[]): number[][] {
let resArr:number[][] = [];
function backTracking(tempArr:number[] = []){
if(tempArr.length === nums.length){
resArr.push(tempArr.slice());
return;
}
for(let i=0; i<nums.length; i++){
if(tempArr.includes(nums[i])) continue;
tempArr.push(nums[i]);
backTracking(tempArr)
tempArr.pop();
}
}
backTracking([])
return resArr;
};
[131] 分割回文串
给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1:
输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]
示例 2:输入:s = "a"
输出:[["a"]]
例如对于字符串abcdef:
- 组合问题:选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中在选组第三个.....。
- 切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中在切割第三段.....。
感受出来了不?
所以切割问题,也可以抽象为一棵树形结构,如图:
递归用来纵向遍历,for循环用来横向遍历,切割线(就是图中的红线)切割到字符串的结尾位置,说明找到了一个切割方法。
此时可以发现,切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。
回溯三部曲
- 递归函数参数
全局变量数组path存放切割后回文的子串,二维数组result存放结果集。 (这两个参数可以放到函数参数里)
本题递归函数参数还需要startIndex,因为切割过的地方,不能重复切割,和组合问题也是保持一致的。
在回溯算法:求组合总和(二) (opens new window)中我们深入探讨了组合问题什么时候需要startIndex,什么时候不需要startIndex。
代码如下:
function backtracking (s, startIndex) {}
- 递归函数终止条件
从树形结构的图中可以看出:切割线切到了字符串最后面,说明找到了一种切割方法,此时就是本层递归的终止终止条件。
那么在代码里什么是切割线呢?
在处理组合问题的时候,递归参数需要传入startIndex,表示下一轮递归遍历的起始位置,这个startIndex就是切割线。
所以终止条件代码如下:
fnction backtracking (s, startIndex) {
// 如果起始位置已经大于s的大小,说明已经找到了一组分割方案了
if (startIndex >= s.length) {
result.push(path);
return;
}
}
- 单层搜索的逻辑
来看看在递归循环,中如何截取子串呢?
在for (int i = startIndex; i < s.size(); i++)
循环中,我们 定义了起始位置startIndex,那么 [startIndex, i] 就是要截取的子串。
首先判断这个子串是不是回文,如果是回文,就加入在vector<string> path
中,path用来记录切割过的回文子串。
代码如下:
for (let i = startIndex; i < s.length; i++) {
if (isPalindrome(s, startIndex, i)) { // 是回文子串
// 获取[startIndex,i]在s中的子串
let str = s.substr(startIndex, i - startIndex + 1);
path.push(str);
} else { // 如果不是则直接跳过
continue;
}
backtracking(s, i + 1); // 寻找i+1为起始位置的子串
path.pop(); // 回溯过程,弹出本次已经填在的子串
}
注意切割过的位置,不能重复切割,所以,backtracking(s, i + 1); 传入下一层的起始位置为i + 1。
判断回文子串
最后我们看一下回文子串要如何判断了,判断一个字符串是否是回文。
可以使用双指针法,一个指针从前向后,一个指针从后先前,如果前后指针所指向的元素是相等的,就是回文字符串了。
那么判断回文的C++代码如下:
bool isPalindrome( s, start, end) {
for (let i = start, j = end; i < j; i++, j--) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
代码:
function partition(s: string): string[][] {
const res: string[][] = []
const path: string[] = []
const isHuiwen = (
str: string,
startIndex: number,
endIndex: number
): boolean => {
for (; startIndex < endIndex; startIndex++, endIndex--) {
if (str[startIndex] !== str[endIndex]) {
return false
}
}
return true
}
const rec = (str: string, index: number): void => {
if (index >= str.length) {
res.push([...path])
return
}
for (let i = index; i < str.length; i++) {
if (!isHuiwen(str, index, i)) {
continue
}
path.push(str.substring(index, i + 1))
rec(str, i + 1)
path.pop()
}
}
rec(s, 0)
return res
};
[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"]
示例 2:输入:s = "0000"
输出:["0.0.0.0"]
示例 3:输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
其实只要意识到这是切割问题,切割问题就可以使用回溯搜索法把所有可能性搜出来,和刚做过的131.分割回文串 (opens new window)就十分类似了。
切割问题可以抽象为树型结构,如图:
回溯三部曲
- 递归参数
在131.分割回文串 (opens new window)中我们就提到切割问题类似组合问题。
startIndex一定是需要的,因为不能重复分割,记录下一层递归分割的起始位置。
本题我们还需要一个变量pointNum,记录添加逗点的数量。
所以代码如下:
// startIndex: 搜索的起始位置,pointNum:添加逗点的数量
function backTracking(tempArr:string[],startIndex:number,s:string)
- 递归终止条件
终止条件和131.分割回文串 (opens new window)情况就不同了,本题明确要求只会分成4段,用切割线切到最后加四段作为终止条件。
if (tempArr.length === 4 && startIndex >= s.length) {
resArr.push(tempArr.join('.'));
return;
}
if (tempArr.length === 4 || startIndex >= s.length) return;
- 单层搜索的逻辑
在131.分割回文串 (opens new window)中已经讲过在循环遍历中如何截取子串。
在for (int i = startIndex; i < s.size(); i++)
循环中 [startIndex, i] 这个区间就是截取的子串,需要判断这个子串是否合法。
如果合法就在字符串后面加上符号.
表示已经分割。
如果不合法就结束本层循环,如图中剪掉的分支:
然后就是递归和回溯的过程:
递归调用时,下一层递归的startIndex要从i+2开始(因为需要在字符串中加入了分隔符.
),同时记录分割符的数量pointNum 要 +1。
回溯的时候,就将刚刚加入的分隔符.
删掉就可以了,pointNum也要-1。
代码如下:
for(let i = startIndex + 1; i <= Math.min(s.length, startIndex + 3); i++){
let n = s.slice(startIndex,i);
if(isValid(n)){
tempArr.push(s.slice(startIndex, i));
backTracking(tempArr,i,s);
tempArr.pop();
}
判断子串是否合法
最后就是在写一个判断段位是否是有效段位了。
主要考虑到如下三点:
- 段位以0为开头的数字不合法
- 段位里有非正整数字符不合法
- 段位如果大于255了不合法
代码如下:
function isValid(str: string): boolean {
let resBool: boolean = true;
let tempVal: number = Number(str);
if (
str.length === 0 || isNaN(tempVal) ||
tempVal > 255 || tempVal < 0 ||
(str.length > 1 && str[0] === '0')
) {
resBool = false;
}
return resBool;
}
代码
function restoreIpAddresses(s: string): string[] {
let resArr:string[] = [];
function isValid(str: string): boolean {
let resBool: boolean = true;
let tempVal: number = Number(str);
if (
str.length === 0 || isNaN(tempVal) ||
tempVal > 255 || tempVal < 0 ||
(str.length > 1 && str[0] === '0')
) {
resBool = false;
}
return resBool;
}
function backTracking(tempArr:string[],startIndex:number,s:string){
if (tempArr.length === 4 && startIndex >= s.length) {
resArr.push(tempArr.join('.'));
return;
}
if (tempArr.length === 4 || startIndex >= s.length) return;
for(let i = startIndex + 1; i <= Math.min(s.length, startIndex + 3); i++){
let n = s.slice(startIndex,i);
if(isValid(n)){
tempArr.push(s.slice(startIndex, i));
backTracking(tempArr,i,s);
tempArr.pop();
}
}
}
backTracking([],0,s)
return resArr
};
[78] 子集
给你一个整数数组
nums
,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3] 输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入:nums = [0] 输出:[[],[0]]
求子集问题和77.组合 (opens new window)和131.分割回文串 (opens new window)又不一样了。
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话,那么组合问题和分割问题都是收集树的叶子节点,而子集问题是找树的所有节点!
其实子集也是一种组合问题,因为它的集合是无序的,子集{1,2} 和 子集{2,1}是一样的。
那么既然是无序,取过的元素不会重复取,写回溯算法的时候,for就要从startIndex开始,而不是从0开始!
有同学问了,什么时候for可以从0开始呢?
求排列问题的时候,就要从0开始,因为集合是有序的,{1, 2} 和{2, 1}是两个集合,排列问题我们后续的文章就会讲到的。
以示例中nums = [1,2,3]为例把求子集抽象为树型结构,如下:
从图中红线部分,可以看出遍历这个树的时候,把所有节点都记录下来,就是要求的子集集合
回溯三部曲
- 递归函数参数
全局变量数组path为子集收集元素,二维数组result存放子集组合。(也可以放到递归函数参数里)
递归函数参数在上面讲到了,需要startIndex。
代码如下:
function backTracking(tempArr:number[],startIndex:number){
递归终止条件
从图中可以看出:
剩余集合为空的时候,就是叶子节点。
那么什么时候剩余集合为空呢?
就是startIndex已经大于数组的长度了,就终止了,因为没有元素可取了,代码如下:
if (startIndex===nums.length) {
return;
}
其实可以不需要加终止条件,因为startIndex >= nums.size(),本层for循环本来也结束了。
- 单层搜索逻辑
求取子集问题,不需要任何剪枝!因为子集就是要遍历整棵树。
那么单层递归逻辑代码如下:
for (int i = startIndex; i < nums.size(); i++) {
path.push_back(nums[i]); // 子集收集元素
backtracking(nums, i + 1); // 注意从i+1开始,元素不重复取
path.pop_back(); // 回溯
}
代码
function subsets(nums: number[]): number[][] {
let resArr : number[][] = [];
function backTracking(tempArr:number[],startIndex:number){
resArr.push([...tempArr]);
if(startIndex===nums.length){
return;
}
for(let i=startIndex; i<nums.length; i++){
tempArr.push(nums[i])
backTracking(tempArr,i+1);
tempArr.pop();
}
}
backTracking([],0)
return resArr;
};
标签:tempArr,递归,number,TS,---,算法,let,回溯,startIndex
From: https://www.cnblogs.com/guibi/p/16714752.html