找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
时间: 2024-05-07 10:16:32 浏览: 13
这是一道经典的回溯算法题。我可以给您分享一个代码实现,可以找到所有相加之和为n的k个数的组合:
```
#include <iostream>
#include <vector>
using namespace std;
void combinationSumHelper(int k, int n, int start, vector<int>& path, vector<vector<int>>& result) {
if (k == 0 && n == 0) {
result.push_back(path);
return;
}
if (k <= 0 || n <= 0) {
return;
}
for (int i = start; i <= 9; i++) {
path.push_back(i);
combinationSumHelper(k-1, n-i, i+1, path, result);
path.pop_back();
}
}
vector<vector<int>> combinationSum(int k, int n) {
vector<vector<int>> result;
vector<int> path;
combinationSumHelper(k, n, 1, path, result);
return result;
}
int main() {
vector<vector<int>> result = combinationSum(3, 7);
for (int i = 0; i < result.size(); i++) {
for (int j = 0; j < result[i].size(); j++) {
cout << result[i][j];
if (j < result[i].size() - 1) {
cout << " + ";
}
}
cout << endl;
}
return 0;
}
```
当输入k=3, n=7时,输出为:
```
1 + 2 + 4
1 + 3 + 3
2 + 2 + 3
```
希望能帮到您。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)