Meet in the Middle

时限1s

空间限制512MB

题目描述

给定 n 和一个长度为 n 的数组，有多少种方法选择一个该数组的子集使得和为 x 。

输入

第一行两个整数 n 和 x ，分别为数组的大小和所需子集和 x 。

第二行包含 n 个数，表示给定的数组。

输出

子集和为 x 的方案数

数据范围

1≤n≤40

1≤x≤109

1≤ti≤109

样例

Input:

4 5

1 2 3 2

Output:

3

本人代码：

#include<bits/stdc++.h>
using namespace std;
int n,k1,k2,last;
long long m,a[40],p[1048576],q[1048576],ans;
void dfs(int now,long long s,bool flag){
    if(s>m) return;
    if(now==last){
        if(flag) p[k1++]=s;
        else q[k2++]=s;
        return;
    }
    dfs(now+1,s,flag);
    dfs(now+1,s+a[now],flag);
}
int main(){
    scanf("%d%lld",&n,&m);
    for(int i=0;i<n;i++) scanf("%lld",&a[i]);
    last=n>>1;
    dfs(0,0,1);
    last=n;
    dfs(n>>1,0,0);
    sort(p,p+k1);
    sort(q,q+k2);
    for(int i=0;i<k1;i++) ans+=upper_bound(q,q+k2,m-p[i])-q;
    printf("%lld",ans);
    return 0;
}

样例输出40，求帮改