るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

PKU 1564 Sum It Up

1564 -- Sum It Up


[問題]
N個の要素からなる集合が与えられます。合計がtとなる任意の部分集合をdecreasing orderで出力してください。

(例)
Input:
t = 400
N = 12
[50 50 50 50 50 50 25 25 25 25 25 25]

Output:
Sums of 400:
50+50+50+50+50+50+25+25+25+25
50+50+50+50+50+25+25+25+25+25+25



[解法]

Nが小さいので普通にやるだけ

vector<int>Nums;
int Sum,N;
map<string,bool>track;
void Print(vector<int> v){
  rep(i,v.size()){
    cout<<v[i];
    if(i == v.size() - 1) cout<<endl;
    else cout<<"+";
  }
}
string VectoString(vector<int>li){
  string res = "";
  rep(i,li.size()){
    char buf[100];
    sprintf(buf,"%d",li[i]);
    string tmp = buf;
    res += tmp;
  }
  return res;
}
int dfs(int index,int sum,vector<int>li){
  if(sum < Sum){
    for(int i = index + 1; i < Nums.size(); i++){
      li.pb(Nums[i]);
      dfs(i,sum + Nums[i],li);
      li.pop_back();
    }
  }
  if(sum == Sum){
    string tr = VectoString(li);
    if(!track[tr]){
      Print(li);
      track[tr] = true;
    }
  } 
}
int main(){
  while(cin>>Sum>>N,N){
    Nums.clear();
    track.clear();
    rep(i,N){
      int tmp; cin>>tmp;
      Nums.pb(tmp);
    }
    vector<int>li;
    printf("Sums of %d:\n",Sum);
    dfs(-1,0,li);

    if(track.empty()) puts("NONE");
       
  }
}