PKU 1564 Sum It Up
http://poj.org/problem?id=1564
n個の数字とtが与えられる。
この時、n個の数字から和がtになるような組み合わせを全て選べというような問題。
全探索する。n<=12なので、最悪でも2^12の計算量で済む・・・はず。
int t,n; bool none; int ins; PI in[12]; int use[12]; void dfs(int ne,int rest){ if(rest==0){ none=false; bool nfir=0; rep(i,ne){ rep(j,use[i]){ if(nfir)cout<<'+'; cout<<in[i].F; nfir=1; } } cout<<endl; return; } if(ne>=ins)return; for(use[ne]=in[ne].S;use[ne]>=0;use[ne]--){ if(use[ne]*in[ne].F>rest)continue; dfs(ne+1,rest-use[ne]*in[ne].F); } } main(){ while(cin>>t>>n,t|n){ cout<<"Sums of "<<t<<':'<<endl; none=true; map<int,int> app; rep(i,n){ int x; cin>>x; app[x]++; } int pos=0; ins=app.size(); FOR(miter,app)in[ins-++pos]=*miter; dfs(0,t); if(none)cout<<"NONE"<<endl; } }