当答案可以分为两半时 为了降低复杂度 可以使用折半搜索
对前半部分 搜出所有可能的和 用map记录
对后半部分 同样也是搜出可能的和 如果前半部分存在一个和 能拼起来 那ans++
#include<bits/stdc++.h> #define N 45 #define ll long long using namespace std; ll n,key,ans,a[N]; map <ll,int> M; void dfs1(int now,int end,ll sum) { if(now>end) { M[sum]++; return; } dfs1(now+1,end,sum); dfs1(now+1,end,sum+a[now]); } void dfs2(int now,int end,ll sum) { if(now>end) { ans+=M[key-sum]; return; } dfs2(now+1,end,sum); dfs2(now+1,end,sum+a[now]); } int main() { cin>>n>>key; for(int i=1;i<=n;i++) cin>>a[i]; dfs1(1,(1+n)/2,0); dfs2((1+n)/2+1,n,0); cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9888774.html
