vector<vector<int>> combine(int n, int k) {
时间: 2023-10-22 15:18:16 浏览: 101
这是一个求组合的问题,给定n个不同的数,从中选取k个数的所有组合。可以使用回溯算法来解决这个问题。
具体步骤如下:
1. 定义一个二维数组res,用于存储所有符合要求的组合。
2. 定义一个一维数组path,用于存储每一次的组合。
3. 定义一个递归函数backtrack,该函数接受三个参数:start表示从哪个数开始选取,path表示当前已选取的数,res表示最终的结果。
4. 在backtrack函数中,首先判断path的长度是否等于k,如果等于k,说明已经选取了k个数,将其加入到res中并返回。
5. 如果path的长度小于k,那么从start开始遍历n个数,将当前的数加入到path中,并递归调用backtrack函数,同时start的值加1,表示从下一个数开始选取。
6. 当递归返回后,将path中最后一个数弹出,继续遍历下一个数。
7. 最后返回res即可。
代码实现如下:
```
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> path;
backtrack(n, k, 1, path, res);
return res;
}
void backtrack(int n, int k, int start, vector<int>& path, vector<vector<int>>& res) {
if (path.size() == k) {
res.push_back(path);
return;
}
for (int i = start; i <= n; i++) {
path.push_back(i);
backtrack(n, k, i + 1, path, res);
path.pop_back();
}
}
```
阅读全文