用C++编程,有n个数,输出其中r(r<=n)个数的所有组合。
时间: 2024-03-24 16:40:13 浏览: 61
可以使用回溯法(backtracking)来解决这个问题,以下是一份C++实现代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
void backtrack(vector<vector<int>>& res, vector<int>& path, int n, int r, int start) {
if (path.size() == r) {
res.push_back(path);
return;
}
for (int i = start; i <= n; i++) {
path.push_back(i);
backtrack(res, path, n, r, i + 1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int r) {
vector<vector<int>> res;
vector<int> path;
backtrack(res, path, n, r, 1);
return res;
}
int main() {
int n = 5, r = 3;
vector<vector<int>> res = combine(n, r);
for (auto& v : res) {
for (auto& num : v) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
```
其中,backtrack函数用于递归搜索所有的组合,res用于存储所有的组合,path用于存储当前的组合,n表示一共有n个数,r表示需要选出r个数,start表示搜索的起点。
在backtrack函数中,首先判断当前已经选择的元素个数是否等于r,如果是,则将当前组合加入res中;否则,从start开始遍历所有可选的元素,并将其加入path中,继续递归调用backtrack函数,直到选择的元素个数等于r或者已经选择了n个元素。
在main函数中,调用combine函数获取所有的组合,并输出结果。
阅读全文