Leetcode 77. 组合 组合型回溯 C++实现

本文主要是介绍Leetcode 77. 组合 组合型回溯 C++实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode 77. 组合

问题：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。

算法：

创建二维返回数组 ans ，和临时数组 path 。

进入 dfs 函数，d 代表还需要选 d 个数字（用一共要选的数字个数 k  减去  已经选过的数字个数，也就是数组 path 的 size）。当 d==0 时证明选完了，执行完就 return 。

进行递归遍历。

代码：

class Solution {
public:vector<vector<int>> combine(int n, int k) {vector<vector<int>> ans;// 返回数组ansvector<int> path;// 临时数组pathauto dfs = [&](auto&&dfs,int i){int d = k - path.size();// 还需要选d个// 选好了if(d == 0){ans.emplace_back(path);// 存入ansreturn;}for(int j = i;j >= d;j--){path.push_back(j);// 存入pathdfs(dfs,j - 1);// 进入下一层递归path.pop_back();// 恢复现场}};dfs(dfs,n);// 递归入口return ans;}
};

 写法2：

class Solution {
public:vector<vector<int>> combine(int n, int k) {vector<vector<int>> ans;vector<int> path;int p = 0;auto dfs = [&](auto &&dfs,int i,int p){if(p == k){ans.emplace_back(path);return ;}for(int j = i;j <= n;j++){path.emplace_back(j);dfs(dfs,j + 1,p + 1);path.pop_back();// path[p++] = j;// dfs(dfs,j + 1,p);// p--;}};dfs(dfs,1,0);return ans;}
};

这篇关于Leetcode 77. 组合 组合型回溯 C++实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---