首先要明确一点回溯也是纯暴力的一种方法,就是多层for循环。但是有的题目你不能写出它具体有多少层for循环,因此用递归来表示内侧for循环的逻辑。
比如说这道题,它for循环的数目是随着K变化的,K等于2是就两层for循环。
卡哥给出回溯算法框架
点击查看代码
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
看这个框架,可以这样理解。for循环代表横向查找的过程,递归代表纵向查找的过程。
终止条件就是收获结果的过程。
该题因为不能插入同样的元素,因此下一层递归时就要跳过那个元素。
因此要在for循环中的起始条件改动,
for(int i=startflag;i<=n;i++),同时递归时startflag++就行。
如果要进行剪枝就要对for循环中的终止条件进行改动
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++)
完整代码
点击查看代码
class Solution {
public:
vector<int>path;
vector<vector<int>>cnt;
void backtracking(int n,int k,int startflag){
if(path.size()==k){
cnt.push_back(path);
return ;
}
for(int i=startflag;i<=n;i++){
path.push_back(i);
backtracking(n,k,i+1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(n,k,1);
return cnt;
}
};