蓝桥杯 ALGO-115 算法训练 和为T
发布时间
阅读量：
阅读量
问题描述
从一个大小为n的整数集中选取一些元素，使得它们的和等于给定的值T。每个元素限选一次，不能一个都不选。
输入格式
第一行一个正整数n，表示整数集内元素的个数。
第二行n个整数，用空格隔开。
第三行一个整数T，表示要达到的和。
输出格式
输出有若干行，每行输出一组解，即所选取的数字，按照输入中的顺序排列。
若有多组解，优先输出不包含第n个整数的；若都包含或都不包含，优先输出不包含第n-1个整数的，依次类推。
最后一行输出总方案数。
样例输入
5
-7 -3 -2 5 9
0
样例输出
-3 -2 5
-7 -2 9
2
数据规模和约定
1 <=n<=22
T<=maxlongint
集合中任意元素的和都不超过long的范围 分析：1.数据规模在n <=22，递归搜索不会超时，每个数字可选择拿或不拿
2.搜索为了保证符合题目顺序，从后向前搜索～
#include <iostream>
#include <vector>
using namespace std;
vector<int> v, ans;
int n, k, cnt;
void dfs(int num, int sum) {
if (num == -1) {
if (sum == k && ans.size() > 0) {
for (int i = ans.size() - 1; i >= 0; i--) {
if (i != 0) {
printf("%d ", ans[i]);
} else {
printf("%d\n", ans[i]);
}
}
cnt++;
}
} else {
dfs(num - 1, sum);
ans.push_back(v[num]);
dfs(num - 1, sum + v[num]);
ans.pop_back();
}
}
int main() {
scanf("%d", &n);
v.resize(n);
for (int i = 0; i < n; i++)
scanf("%d", &v[i]);
scanf("%d", &k);
dfs(n - 1, 0);
printf("%d\n", cnt);
return 0;
}全部评论 (0)
还没有任何评论哟~