代码随想录算法训练营第24天|理论基础|77. 组合
第七章 回溯算法part01
● 理论基础
● 77. 组合
理论基础
其实在讲解二叉树的时候,就给大家介绍过回溯,这次正式开启回溯算法,大家可以先看视频,对回溯算法有一个整体的了解。
题目链接/文章讲解:https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
视频讲解:https://www.bilibili.com/video/BV1cy4y167mM
- 组合
对着 在 回溯算法理论基础 给出的 代码模板,来做本题组合问题,大家就会发现 写回溯算法套路。
在回溯算法解决实际问题的过程中,大家会有各种疑问,先看视频介绍,基本可以解决大家的疑惑。
本题关于剪枝操作是大家要理解的重点,因为后面很多回溯算法解决的题目,都是这个剪枝套路。
题目链接/文章讲解:https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html
视频讲解:https://www.bilibili.com/video/BV1ti4y1L7cv
剪枝操作:https://www.bilibili.com/video/BV1wi4y157er
class Solution {
public:
vector<vector<int>> result;// 存放符合条件结果的集合
vector<int> path;// 用来存放符合条件结果
void backtracking(int n,int k,int startindex)
{
if(path.size()==k)
{
result.push_back(path);
return;
}
for(int i=startindex;i<=n;i++)//for (int i = startIndex; i <= n - (k - path.size()) + 1; i++)剪枝方法
{
path.push_back(i); // 处理节点
backtracking(n,k,i+1);// 递归
path.pop_back();// 回溯,撤销处理的节点
}
}
vector<vector<int>> combine(int n, int k) {
result.clear();// 可以不写
path.clear();// 可以不写
backtracking(n,k,1);
return result;
}
};
/*
//回溯算法模板
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
//剪枝总结
接下来看一下优化过程如下:
已经选择的元素个数: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 (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置
*/```