系列文章目录
代码随想录——回溯
文章目录
- 系列文章目录
- 概述
- 组合
- 组合
- 组合III
- 电话号码的字母组合
- 组合总和
- 组合总和II
- 分割
- 分割回文串
- ** 复原ip地址
- 子集
- 子集
- 子集II
概述
回溯的本质就是递归遍历,但在完成某一条路之后会撤回到上一层,然后重新选择另一条路继续遍历,是一个比较低效的算法,能进行提升的方式就是剪枝。
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果}
}
组合
组合
链接:https://leetcode.cn/problems/combinations/description/
vector<vector < int > > 作为最终返回的结果,vector < int >作为每一小项,中止条件是vector< int > == k,注意在递归过程中n,k是不变的,所以必须引入一个递增index来去重。
剪枝方法:
- 已经选择的元素个数:path.size();
- 还需要的元素个数为: k - path.size();
- 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1,开始遍历
组合III
链接:https://leetcode.cn/problems/combination-sum-iii/description/
与前一个组合几乎一样,但中止条件需要加一个total == k的判断。
电话号码的字母组合
链接:https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
中止条件是单个项的size等于digits的size,一开始我以为要双循环,即digits遍历和单个数字对应的字母遍历,但其实不需要,因为digits一定是顺序往后取的,所以只需要定义一个index,每层递归+1即可。
ps:在leetcode由char转变为int的方法是减去 ‘0’
num[digits[index] - '0'
组合总和
链接:https://leetcode.cn/problems/combination-sum/description/
中止条件为当总和相等时push进result并return,总和超过target时直接人return;注意这道题也是不能重复的,一般不能重复的都需要加入index来保证起始位置。
组合总和II
链接:https://leetcode.cn/problems/combination-sum-ii/description/
这道题不重复的核心点在于,同层的数不能够重选,例如[1,1,2,2,5],第一层选了1,第二层还是可以继续选1,因为两者不是同层的。但如果第一层的第一个1用完了,又选了第二个1,这就重复了,所以只需要加一个判断条件:
if (i > index && candidates[i] == candidates[i - 1]) {continue;}
这里的核心点在于ℹi > index,因为index是本层的第一个数,必然不可能重复,所以要从index下一个开始判断,此时如果第二个数和第一个数是相同的,则属于同层重复选择,直接continue;
分割
分割回文串
https://leetcode.cn/problems/palindrome-partitioning/description/
每切下来一个子字符串,就相当于是在一层做了选择,这样就可以套上回溯算法的模板。中止条件是起始切割位置到了字符串的最后一位,额外再写一个回文判断函数。、
注意:leetcode里常用的切割字符串函数substr,第一个参数是起始位置,第二个参数是要切割的长度。
string str = s.substr(index,i - index + 1);
** 复原ip地址
https://leetcode.cn/problems/restore-ip-addresses/description/
这道题一直做错,能接受的方法是,将切割每一个子字符串进行判断,符合标准后放入vector备用,个数达到4个并且index也等于s.size()之后,再拼接放入最终的result里。
注意:string转为int直接用stoi函数
return stoi(s) <= 255;
字符串的增加和删改不能用-=和+=,要用insert和erase。
子集
子集
https://leetcode.cn/problems/subsets/description/
这道题唯一要注意的点是子集的大小是不固定的,所以不能在中止条件里面将子集添加到结果里,每一次循环都要添加,所以放在递归的开头。中止条件是index == s.size()。
子集II
https://leetcode.cn/problems/subsets-ii/description/
这题和之前组合的去重思路一模一样,在子集的基础上,首先对nums进行sort保证是递增的,然后进行判断去掉本层重复的选择。
if(i > index && nums[i] == nums[i - 1]) continue;