求36个数中选哪些数之和为 s。
2^36 很大,2^18 = 26144,预处理出前18位所有组合,然后再处理后18位
#include <bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,int> q;
int n;
ll s,a[50],sum;
int main()
{
scanf("%d %lld",&n,&s);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
int mid = n/2;
for(int i=1;i<=(1<<mid);i++){
sum = 0;
for(int j=0;j<mid;j++){
if((i>>j)&1)
sum+=a[j+1];
}
q[sum] = i;
}
for(int i=1;i<=(1<<(n-mid));i++){
sum = 0;
for(int j=0;j<(n-mid);j++){
if((i>>j)&1)
sum+=a[mid+j+1];
}
if(q[s-sum]){
ll k = q[s-sum];
for(int j=0;j<mid;j++){
if((k>>j)&1)printf("1");
else printf("0");
}
for(int j=0;j<mid;j++){
if((i>>j)&1)printf("1");
else printf("0");
}
break;
}
}
return 0;
}