![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0gTMx81dsQWZ4lmZf1GLlpXazVmcvwFciV2dsQXYtJ3bm9CX9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5SN5UTO0EzMkVmN1YGO5MzYyYzX1QDM1kDM1AzLcdDMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)
双向搜索
将前一半所有的存下来, 在枚举后一半,枚举完后一半后找前一半的数组是否存在 k-(后一半)
存在,则ans加上(k-后一半)的个数
这里用unordered_map来存
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define N 50
#define ll long long
using namespace std;
using namespace tr1;
int n,k; ll a[N],ans;
unordered_map<ll,int> S;
void dfs1(int u,int d,ll s){
if(s>k) return;
if(u>d){S[s]++;return;}
dfs1(u+1,d,s); dfs1(u+1,d,s+a[u]);
}
void dfs2(int u,int d,ll s){
if(s>k) return;
if(u>d){
if(S.find(k-s)!=S.end()) ans+=S[k-s]; return;
}
dfs2(u+1,d,s); dfs2(u+1,d,s+a[u]);
}
int main(){
freopen("1.in","r",stdin);
freopen("myself.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
dfs1(1,n/2,0); dfs2(n/2+1,n,0);
printf("%lld\n",ans); return 0;
}