Day 8:77 组合

本文主要是介绍Day 8:77 组合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目描述

77 组合

2. 解题思路

该题可以使用回溯类型的模板来解决，注意到可以进行剪枝操作。

3. 代码实现

class Solution {vector<vector<int>> res;vector<int> path;
public:vector<vector<int>> combine(int n, int k) {function<void(int)> dfs = [&](int idx) {// 剪枝if (path.size() + (n - idx + 1) < k) {return;}// if (idx == n + 1) {//     return;// }if (path.size() == k) {res.push_back(path);return;}// 选path.push_back(idx);dfs(idx + 1);path.pop_back();// 不选dfs(idx + 1);};dfs(1);return res;}
};

4. 回溯模板

回溯三部曲

1. 递归函数的返回值以及参数；
2. 回溯函数终止条件；
3. 单层搜索的过程。

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

这篇关于Day 8:77 组合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---