给定一个整数t和n个整数的集合list,将list中的数相加使其和值为t,给出所有的组合。输入包含一个或多组测试数据。每组测试数据占一行,每行的第一个数据为t,第二个数据为n,后面紧跟n个整数,为list中的数据。N=0则表示输入结束,T是一个小于1000的正整数,n是1~12之间的正整数,list中的数小于100大于0,所有数之间用空格隔开,List中数可能重复且无序输入。对于每一组测试数据,输出对应的加法表达式,每个表达式占一行。c++程序
时间: 2024-02-21 19:00:01 浏览: 104
以下是使用回溯法解决此问题的C++代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
void backtrack(vector<int>& nums, int target, int start, vector<int>& path, vector<vector<int>>& res) {
if (target < 0) return; // 如果目标值小于0,返回
if (target == 0) { // 如果目标值等于0,说明已经找到一组解
res.push_back(path);
return;
}
for (int i = start; i < nums.size(); ++i) { // 从start开始遍历所有可能的元素
if (i > start && nums[i] == nums[i - 1]) continue; // 如果当前元素与上一个元素相同,跳过
path.push_back(nums[i]);
backtrack(nums, target - nums[i], i + 1, path, res); // 递归调用,更新目标值和起始位置
path.pop_back(); // 回溯
}
}
int main() {
int t, n;
while (cin >> t >> n && n != 0) {
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
sort(nums.begin(), nums.end()); // 先将数组排序,方便去重
vector<int> path;
vector<vector<int>> res;
backtrack(nums, t, 0, path, res);
cout << "Sums of " << t << ":" << endl;
if (res.empty()) cout << "NONE" << endl;
else {
for (auto& r : res) {
for (int i = 0; i < r.size(); ++i) {
cout << r[i];
if (i != r.size() - 1) cout << "+";
}
cout << endl;
}
}
}
return 0;
}
```
阅读全文