手机网站加百度地图,电子商务网站建设具体方案,网站备案购买,广州网站优化排名哪家好目录 0 引言1 回溯算法基础理论1.1 回溯算法模板1.2 2 组合2.1 我的解题2.2 剪枝操作 #x1f64b;♂️ 作者#xff1a;海码007#x1f4dc; 专栏#xff1a;算法专栏#x1f4a5; 标题#xff1a;算法刷题Day23 | 回溯算法基础理论、 77. 组合❣️ 寄语#xff1a;书… 目录 0 引言1 回溯算法基础理论1.1 回溯算法模板1.2 2 组合2.1 我的解题2.2 剪枝操作 ♂️ 作者海码007 专栏算法专栏 标题算法刷题Day23 | 回溯算法基础理论、 77. 组合❣️ 寄语书到用时方恨少事非经过不知难 0 引言
没错忙完腾讯面试我胡汉三又回来了哈哈加油
1 回溯算法基础理论 文档讲解 视频讲解 做题状态 1.1 回溯算法模板
在递归中有三部曲
递归函数的参数和返回值递归函数终止的条件单层递归的逻辑
回溯三部曲
回溯函数返回值和参数函数名一般为 backtracking返回值一般为 void。再来看一下参数回溯算法的参数不像二叉树递归你们容易一次性确定下来所以一般先写逻辑然后需要什么参数就填什么参数。回溯函数的终止条件判断是否满足终止条件满足的话先将结果保存然后再 return。单层回溯的逻辑选择、递归、撤回选择
代码模板如下
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}1.2
2 组合 文档讲解 视频讲解 做题状态 组合和排列的区别组合的话 {12} 和 {21} 是同样的结果但是在排列中就是两种结果。
2.1 我的解题
有了之前递归的基础再来写回溯就觉得还是可以理解的。回溯算法中的单层回溯往往涉及一个for循环因为我们是将回溯问题转换成了一个n叉树来解决所以要遍历当前层数的所有分支。而在之前二叉树的题目中因为树的分支就两个所以在单层递归逻辑中直接就是分别调用左右子树进行两次递归就行。
class Solution {
public:// 1. 参数和返回值void backTracing(int n, int k, int startIndex, vectorint path, vectorvectorint res){// 2. 递归终止条件if (path.size() k){res.push_back(path);return;}// 3. 单层回溯逻辑for (int i startIndex; i n; i){path.push_back(i);backTracing(n, k, i1, path, res);path.pop_back();}}vectorvectorint combine(int n, int k) {vectorvectorint res;vectorint path;backTracing(n, k, 1, path, res);return res;}
};2.2 剪枝操作
剪枝的原理我们要搜索一个大小为n的集合结果但是此时剩余需要判断的元素已经不足n了。就拿刚才的代码距离当n为4k也为4的时候。假如此时的 startIndex为 2当前 path 的元素个数为 1 。就代表这个分支怎么组合都不可以会出现path元素个数等于4的情况。此时这个分支就可以去除了。 代码如下只修改了单层回溯逻辑的代码增加了一个剪枝的操作。 // 3. 单层回溯逻辑// 先进行剪枝int maxCount n - startIndex 1 path.size();if (maxCount k){return;}for (int i startIndex; i n; i){path.push_back(i);backTracing(n, k, i1, path, res);path.pop_back();}
