蓝桥杯 和为T dfs 二进制枚举

问题描述

　　从一个大小为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的范围

又是基础题没有做出来。

参考自https://blog.csdn.net/S_999999/article/details/103390025

解法一dfs：假如我们从第一个数开始判断选还是不选然后往后搜索的话，也能做出来，不过不满足优先输出不包含后面的数的方案这个前提。所以我们从最后一个数开始往前搜索，并且在dfs内部，不选这个数的情况要在选这个数的代码上面。

#include <bits/stdc++.h>
using namespace std;
vector<int> ans; //存储选了哪些数 
int nums[30];  //存储输入的整数集
int n, T;
int cnt; //总方案数
void dfs(int id, int sum) { //id表示当前遍历到的数的下标，sum表示当前已经选择的数的总和 
    if (id == -1) { //如果搜索完了 
        if (sum == T && ans.size() > 0) { //如果和为T且至少选了一个数 
            for (int i = ans.size() - 1; i >= 0; i--) {  
                cout << ans[i] << " ";
            }
            cout << endl;
            cnt++;
        }
        return; 
    } 
    dfs(id - 1, sum); //不选这个数 
     
    ans.push_back(nums[id]); //选这个数，把这个数加入到ans中 
    dfs(id - 1, sum + nums[id]); //dfs下一层 
    ans.pop_back(); //回溯 
    
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    cin >> T;
    dfs(n - 1, 0); //从最后一个数开始往前搜索 
    cout << cnt << endl;
    return 0;
}

解法二：二进制枚举所有情况，参考自https://blog.csdn.net/z93478462/article/details/81193311

这一题可以用二进制枚举的思想。

比如从5个数字中选择几个的话，每个数字都有选或不选两种情况。

我们用数字0表示不选这个数，用数字1表示选这个数。

所以我们用一个5位数字的二进制01串，就可以表示出所有情况。

00000表示5个数字一个都不选，11111表示5个数字都选。

把题目给出的5个数字依次存入a[0], a[1], a[2], a[3], a[4]

比如以10011分析。我们从右往左看看当前这一位的数字是0还是1。

我们人为规定一下顺序。

10011&1 结果为1即题目给出的第一个数被选中 即是下标为0的数组元素被选中

10011&10 结果为1即题目给出的第二个数被选中  即是下标为1的数组元素被选中

10011&100 结果为0即题目给出的第三个数未被选中  即是下标为2的数组元素未被选中

10011&1000 结果为0即题目给出的第四个数未被选中  即是下标为3的数组元素未被选中

10011&10000 结果为1即题目给出的第五个数被选中  即是下标为4的数组元素被选中

这样顺序反一下，我们从00000到00001到00010到11111，就可以保证题目所要求的优先不选择位置靠后的元素。

#include <bits/stdc++.h>
using namespace std;
int a[30];
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int T;
    cin >> T;
    int ans = 0;
    for (int i = 0; i < (1 << n); i++) { //从0～2^n-1个状态
        int num = 0;
        for (int j = 0; j < n; j++) { //遍历二进制的每一位
            if (i & (1 << j)) { //判断二进制第j位是否存在
                num += a[j]; //如果存在加上第j个元素
            }
        }
        if (num == T && i != 0) { //如果等于结果便将结果输出并将result加一 
            for(int j = 0; j < n; j++) { 
                if (i & (1 << j)) { 
                    cout << a[j] << " ";
                }
            }
            ans++;
            cout << endl;
        }
    }
    cout << ans << endl;
    return 0;
}