目前做那些网站致富,修车店怎么做网站,手机网站建设资讯,wordpress子主题视频1.理论基础 题目链接/文章讲解#xff1a;代码随想录 视频讲解#xff1a;带你学透回溯算法#xff08;理论篇#xff09;| 回溯法精讲#xff01;_哔哩哔哩_bilibili 来自代码随想录的网站#xff1a;
void backtracking(参数) {if (终止条件) {存放结果;return;}for (…1.理论基础 题目链接/文章讲解代码随想录 视频讲解带你学透回溯算法理论篇| 回溯法精讲_哔哩哔哩_bilibili 来自代码随想录的网站
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}所以回溯法都可以转换成一个n叉树的树形结构集合的大小就是子树的宽度 递归的深度就是树的深度。 2.组合 题目链接/文章讲解 代码随想录 视频讲解带你学透回溯算法-组合问题对应力扣题目77.组合| 回溯法精讲_哔哩哔哩_bilibili 剪枝操作带你学透回溯算法-组合问题的剪枝操作对应力扣题目77.组合| 回溯法精讲_哔哩哔哩_bilibili 代码未剪枝
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(int n,int k,int startIndex){// 递归返回条件if(path.size() k){result.push_back(path);return;}// 遍历n叉树里的结点for(int i startIndex;i n;i){path.push_back(i);backtracking(n,k,i 1);path.pop_back();}}vectorvectorint combine(int n, int k) {backtracking(n,k,1);return result;}
};
代码剪枝版
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(int n,int k,int startIndex){// 递归返回条件if(path.size() k){result.push_back(path);return;}// 遍历n叉树里的结点for(int i startIndex;i n - (k - path.size() - 1);i){path.push_back(i);backtracking(n,k,i 1);path.pop_back();}}vectorvectorint combine(int n, int k) {backtracking(n,k,1);return result;}
};
思路剪枝的情况就是我们所能选择的数值的数目已经小于提上要求的组合大小这种情况可以剪掉。
以前for循环里i n ,现在我们要求出剩余数字的数目不少于n的开始下标即 n - (k - path.size() - 1)。这里用总数目减去已经用过的数字个数即 k - path.size() - 1。减1是因为我们开始时的下标为1已经默认用了一个元素了。
其实这种套模板的题还是很省脑的什么
