PKU 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"); } }