回溯理论基础
回溯和递归是相辅相成的，只要有递归就有回溯（执行完一次递归就自动回溯到上一层）
回溯的效率
回溯不是一个高效的算法，而是一个纯暴力的过程
有些问题没有更好的解法，只能使用暴力搜索，这时就可以使用回溯法。包括以下问题：
1、组合问题
2、切割问题
3、子集问题
4、排列问题
5、棋盘问题（N皇后、解数独等）
如何理解回溯法
回溯法解决的问题都可以抽象为树形结构（N叉树）
回溯法的模板
void backtracking( 参数 ){
// 终止条件
if( 终止条件 ){
收集结果（通常在叶子节点收集结果）
return;
}
// 单层逻辑（通常为一个for循环，每次循环都继续递归）
for(集合元素集){
// 处理节点的操作
// 递归
// 回溯（还原，撤销对节点的操作）
}
}回溯三部曲：
1、确定递归函数的参数与返回值：返回值一般是void
2、确定递归的终止条件
3、确定单层递归的逻辑
77.组合
思考了挺久，最后按模板做出来了（开心）
剪枝操作挺难想明白的
回溯三部曲：
· 参数：
vector<vector<int>> ans：存放最终结果的全局变量
vector<int> cur：当前路径下的组合（也可以设置为全局变量）
int num：当前已经完成搜索的值，本次递归中从num + 1开始搜索
int& k，int& n：题意中的k与n
· 终止条件：组合中的元素个数等于k，说明完成组合，将结果进行保存并返回
· 单层逻辑：
节点操作：当前组合（cur）中添加当前值（i）
递归：i已经完成操作，传入i+1进行递归
回溯：i在该位置的所有组合已经收集完成，将i弹出当前组合
· 剪枝条件：
原循环终止条件：i <= n;
剪枝后的终止条件： i <= n – (k – cur.size()) + 1
剪枝条件即：n – i + 1 >= k – size
· n – i + 1代表当前序列中还剩下的元素个数（+1代表包括了当前节点）
· k – size代表组合中还需要几个元素
· 所以整个剪枝的含义为：当前序列中剩余的元素需要大于等于组合中还缺的元素个数
vector<vector<int>> ans;
void backtracking(int num, int& k, int& n, vector<int> cur) {
// 终止条件：数组长度为k
if (cur.size() == k) {
// 保存结果
ans.push_back(cur);
return;
}
for (int i = num + 1; i <= n - (k - cur.size()) + 1; ++i) {
// 进行节点操作
cur.push_back(i);
// 递归
backtracking(i, k, n, cur);
// 还原节点操作（回溯）
cur.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(0, k, n, {});
return ans;
}
原文地址:https://blog.csdn.net/Y_Vollerei/article/details/136027119
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_67433.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
