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;
  }
}