广西企业网站建设,公司简介50字,公司的网站怎么建设,浙江省建设网站首页回溯的理论基础
其实在讲解二叉树的时候#xff0c;就给大家介绍过回溯#xff0c;这次正式开启回溯算法#xff0c;大家可以先看视频#xff0c;对回溯算法有一个整体的了解。
题目链接/文章讲解 视频讲解
回溯的总结#xff1a;
树的深度#xff08;递归的层数就给大家介绍过回溯这次正式开启回溯算法大家可以先看视频对回溯算法有一个整体的了解。
题目链接/文章讲解 视频讲解
回溯的总结
树的深度递归的层数 树的深度就是要取的数据的个数通过path的size判断是否收集到足够的数据 树的宽度循环的范围 输的宽度就是搜索的范围就是for循环的循环范围这个范围可以做剪枝操作 递归和回溯就是在这颗树上做搜索深度优先
回溯的函数
退出条件 收集到足够的数据也就是到达了指定的深度 递归 每一个递归就是给一个范围获取一个数字递归的获取数字到了指定的数量深度结束递归 循环 进入下一个循环的时候需要回溯将上一个递归获取的数据pop掉用来接收下一个数据 剪枝 1 对循环的范围做剪枝 2 根据对数据的要求做做剪枝
回溯函数的模板
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}组合
leetcode题目链接 题目链接/文章讲解 视频讲解 剪枝操作
//未剪枝
class Solution {
private:vectorvectorint result; // 存放符合条件结果的集合vectorint 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) {path.push_back(i); // 处理节点backtracking(n, k, i 1); // 递归path.pop_back(); // 回溯撤销处理的节点}}
public:vectorvectorint combine(int n, int k) {result.clear(); // 可以不写path.clear(); // 可以不写backtracking(n, k, 1);return result;}
};//剪枝操作代码优化
class Solution {
private:vectorvectorint result; // 存放符合条件结果的集合vectorint 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) {path.push_back(i); // 处理节点backtracking(n, k, i 1); // 递归path.pop_back(); // 回溯撤销处理的节点}}
public:vectorvectorint combine(int n, int k) {result.clear(); // 可以不写path.clear(); // 可以不写backtracking(n, k, 1);return result;}
};
