密碼[雙向搜尋][STL[unordered_map]]

雙向搜尋

将前一半所有的存下來, 在枚舉後一半,枚舉完後一半後找前一半的數組是否存在 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;
}