蓝桥杯 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;
}

#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;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版