理论基础
题目链接/文章讲解: 代码随想录
回溯算法本质就是穷举,加上一些剪枝操作,但不是什么高效的算法。有递归就会有回溯,同时一层递归就是一层for循环
解决的问题
回溯法,一般可以解决如下几种问题:
- 组合问题:N个数里面按一定规则找出k个数的集合
- 切割问题:一个字符串按一定规则有几种切割方式
- 子集问题:一个N个数的集合里有多少符合条件的子集
- 排列问题:N个数按一定规则全排列,有几种排列方式
棋盘问题:N皇后,解数独等
如何理解回溯法
可以抽象为一个N叉树,树的宽度就是集合的大小,用for循环来处理,树的深度就是递归处理
递归函数一般都是
void backtracking(参数)
{
if(终止条件){ //通常都是叶子节点了
收集结果
}
return;
//单层逻辑
for(集合的元素)
{
处理节点
递归函数
回溯操作(撤销处理节点的操作)
}
return;
}
77、组合
题目链接/文章讲解:代码随想录
解题思路
依靠回溯三部曲来写一段代码,第一步是递归函数参数和返回值
第二步是确定终止条件
第三部是单层递归逻辑
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
public:
void backtracking(int n, int k, int startIndex) //startIndex来用记录从哪里开始搜
{
//终止条件,当path的数量和k相等了,就是要收获结果了
if(path.size()==k)
{
result.push_back(path);
return;
}
for(int i=startIndex; i <= n ; i++)
{
path.push_back(i);
backtracking(n,k,i+1); //传入的是i+1,告诉下一层要开始遍历的位置
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(n,k,1);
return result;
}
};
- 时间复杂度: O(n * 2^n)
- 空间复杂度: O(n)
剪枝优化
举一个例子,n = 4,k = 4的话,那么第一层for循环的时候,从元素2开始的遍历都没有意义了。 在第二层for循环,从元素3开始的遍历都没有意义了。
所以,可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了,那么就没有必要搜索了。
我们还要搜索k-path.size()个,一共是n个,那么我们的i最多不能超过 n - (k-path.size()) +1 个,因为是左闭,需要加一,就例如我们有4个元素,还需要搜2个,那么最多到3搜,才是有意义的,到4就已经搜不到了,个数不够了。
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
public:
void backtracking(int n, int k, int startIndex) //startIndex来用记录从哪里开始搜
{
//终止条件,当path的数量和k相等了,就是要收获结果了
if(path.size()==k)
{
result.push_back(path);
return;
}
for(int i=startIndex; i <= n - (k-path.size()) +1 ; i++) //剪枝剪在for循环的范围内,这样才不会去增加横向宽度比较
{
path.push_back(i);
backtracking(n,k,i+1); //传入的是i+1,告诉下一层要开始遍历的位置
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(n,k,1);
return result;
}
};
收获
开启回溯,冲冲冲