东莞网站建设lhznkj,服饰类网站开发项目,高端网站制造,个人申请公众号注册代码随想录二刷Day24
今日任务
理论基础 77.组合 语言#xff1a;C
理论基础
解决的问题 ① 组合问题#xff1a;不考虑顺序 ② 切割问题 ③ 子集问题 ④ 排列问题#xff1a;考虑顺序 ⑤ 棋盘问题#xff1a;N皇后#xff0c;解数独回溯法三部曲 ① 回溯函数模板返回…代码随想录二刷Day24
今日任务
理论基础 77.组合 语言C
理论基础
解决的问题 ① 组合问题不考虑顺序 ② 切割问题 ③ 子集问题 ④ 排列问题考虑顺序 ⑤ 棋盘问题N皇后解数独回溯法三部曲 ① 回溯函数模板返回值以及参数 函数名backtracking 返回值void 参数先写逻辑再确定需要什么参数 ② 回溯函数终止条件搜索到叶子节点 ③ 回溯搜索的遍历过程for循环是横向遍历backtracking递归是纵向遍历回溯模板
void backtracking(参数){if(终止条件){存放结果;return;}for(选择本层集合中的元素(树中节点孩子的数量就是集合的大小)){处理节点;backtracking();回溯撤销处理结果;}
}77. 组合
链接https://leetcode.cn/problems/combinations/
class Solution {
public:vectorvectorint res;vectorint combination;//curLen没有必要直接combination.size()即可void backtracking(int n, int k, int cur, int curLen){if(curLen k){res.push_back(combination);return;}for(int i cur; i n; i){combination.push_back(i);backtracking(n, k, i 1, curLen 1);combination.pop_back();}}vectorvectorint combine(int n, int k) {backtracking(n, k, 1, 0);return res;}
};剪枝优化
class Solution {
public:vectorvectorint res;vectorint combination;void backtracking(int n, int k, int cur){if(combination.size() k){res.push_back(combination);return;}//循环终止条件优化for(int i cur; i n - (k - combination.size()) 1; i){combination.push_back(i);backtracking(n, k, i 1);combination.pop_back();}}vectorvectorint combine(int n, int k) {backtracking(n, k, 1);return res;}
};可以看到剪枝优化后效率有了很大提升
