C++14(g++5.4) 解法, 执行用时: 997ms, 内存消耗: 33292K, 提交时间: 2019-08-16 10:26:47

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


ll a[37];
ll b[37];
map <ll,string> M;

int main(){
	int n;ll sum;cin>>n>>sum;
	for(int i=0;i<n/2;i++)	cin>>a[i];
	for(int i=n/2;i<n;i++) cin>>b[i-n/2];
	for(int i=0;i<(1<<(n/2));i++)
	{
		string s;ll tmp=0;
		for(int j=0;j<(n/2);j++)
		{
			if((i>>j)&1) s+='1',tmp+=a[j];
			else s+='0';
		}
		M[tmp]=s;
	}
	for(int i=0;i<(1<<(n-n/2));i++)
	{
		string s;ll tmp=0;
		for(int j=0;j<(n-n/2);j++){
			if((i>>j)&1) s+='1',tmp+=b[j];
			else s+='0';
		}
		if(M.count(sum-tmp))
		{
			cout <<M[sum-tmp]<<s;
			break;
		}
	} 
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 460ms, 内存消耗: 31284K, 提交时间: 2022-10-07 13:40:25

#include <bits/stdc++.h>
using namespace std;typedef long long ll;ll n,s,a[105];map<ll,ll>flag;void solve(ll a,ll k){int p[50],ans=0;while(ans<=k){p[++ans]=a%2;a/=2;}for(int i=1;i<ans;i++)printf("%d",p[i]);}int main(){scanf("%lld%lld",&n,&s);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);ll k=(n+1)/2;for(int i=0;i<(1<<k);i++){ll ans=0;for(int j=0;j<k;j++)if(i&(1<<j))ans+=a[j+1];flag[ans]=i;}ll u=n-k;for(int i=0;i<(1<<u);i++){ll ans=0;for(int j=0;j<u;j++)if(i&(1<<j))ans+=a[j+1+k];if(flag[s-ans]!=0){solve(flag[s-ans],k),solve(i,u);break;}}return 0;}

C++11(clang++ 3.9) 解法, 执行用时: 413ms, 内存消耗: 16888K, 提交时间: 2019-08-16 16:35:30

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll>mp;
ll a[50],s,n;
ll check(int x,int k){
	ll res=0;
	while(x){
		res+=(x%2)*a[k];
		x/=2;
		k++;
	}
	return res;
}
void output(int x,int cnt){
	while(cnt--){
		cout<<x%2;
		x/=2;
	}
}
int main(){
	cin>>n>>s;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=0;i<(1<<n/2);++i){
		mp[check(i,1)]=i;
	}
	for(int i=0;i< 1<<(n-n/2);++i){
		ll t=check(i,n/2+1);
		if(mp.count(s-t)){
			output(mp[s-t],n/2);
			output(i,n-n/2);
			return 0;
		}
	}

}

Python3 解法, 执行用时: 1986ms, 内存消耗: 35840K, 提交时间: 2023-01-02 10:33:01

mp=dict()
n,s=map(int,input().split())
a=list(map(int,input().split()))
h=n//2
for i in range(0,1<<h,1):
    ts=0
    for j in range(0,h,1):
        if(i>>j&1):
            ts+=a[j]
    mp[ts]=i
ans=0
for i in range(0,1<<h,1):
    ts=0
    for j in range(0,h,1):
        if(i>>j&1):
            ts+=a[j+h]
    if (s-ts) in mp:
        ans=(i<<h)|(mp[s-ts])
        break
for i in range(0,n,1):
    print((ans>>i&1),end="")    
print()