题解 | 神奇的口袋

#include <stdio.h>
#include <vector>
using namespace std;
int ans = 0; //总的方式数
int res = 0; //DFS递归过程中的累加和
int n;
vector<int> num; //存储数据
vector<long long> sum;  //存储数据对应的后缀和
void DFS(int pos) //深度优先遍历
{
    if(res > 40 || res+sum[pos] < 40) //剪枝
    {
        return;
    }
    if(pos==n) //递归结束条件
    {
        if(res==40) //n项相加等于40
        {
            ans++;
        }
        return;
    }
    //选当前数
    res += num[pos];
    DFS(pos+1);
    res -= num[pos]; //回溯
    //不选当前数
    DFS(pos+1);
}
int main()
{
    scanf("%d",&n);
    num.resize(n); //读入之前要设置num数组的长度为n ，全局变量的处理
    for(int i = 0 ; i < n ; i++)
    {
        scanf("%d",&num[i]);
    }
    int count = 0;
    sum.resize(n); //设置sum的长度为n,可以使用下标进行访问
    for(int i = n-1 ; i >=0 ; i--) //后缀和（下标从0开始） //若从最后开始则求前缀和
    {
        count += num[i];
        sum[i] = count; 
    }
    DFS(0);
    printf("%d\n",ans);
    return 0;
}