UVa 574 Sum It Up

题目描述题目要求从给定列表中找出所有不同的子集其和等于目标数ttt。列表中的数字按非递增顺序给出可能有重复。输出时每个子集中的数字按非递增顺序排列且子集之间按字典序降序排列即第一个数字大的优先相同则比较第二个依此类推。若无解输出NONE。输入格式输入包含多个测试用例每行一个。每行第一个整数ttt第二个整数nnn后面nnn个整数。若n0n 0n0则输入结束。t1000t 1000t10001≤n≤121 \le n \le 121≤n≤12每个数100 100100。输出格式对于每个测试用例先输出Sums of t:然后每行一个子集数字之间用连接按降序排列。若无解输出NONE。样例输入4 6 4 3 2 2 1 1 5 3 2 1 1 400 12 50 50 50 50 50 50 25 25 25 25 25 25 25 0 0输出Sums of 4: 4 31 22 211 Sums of 5: NONE Sums of 400: 50505050505025252525 5050505050252525252525题目分析本题的核心是子集和问题由于n≤12n \le 12n≤12可以使用回溯法枚举所有子集。回溯算法按顺序遍历列表每个数字可选或不选。由于数字可能有重复使用集合solutionssolutionssolutions去重。回溯时若当前和等于ttt则将所选数字组成的字符串加入集合。若当前和大于ttt则剪枝。输出排序由于列表本身是非递增顺序且回溯按顺序选择生成的子集自然满足降序。但需要去重后按降序输出可以使用集合自动排序字符串字典序降序对应数字降序。复杂度分析最多21240962^{12} 40962124096种子集可接受。代码实现// Sum It Up// UVa ID: 574// Verdict: Accepted// Submission Date: 2016-08-17// UVa Run Time: 0.040s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intnumber[12],visited[12],t,n,counter;string text[12];setstringsolutions;voiddfs(intdepth,intsum){if(sumt){string sequence;boolfirst_numbertrue;for(inti0;in;i)if(visited[i]){if(first_number)first_numberfalse;elsesequence;sequencetext[i];}if(solutions.find(sequence)solutions.end()){coutsequence\n;solutions.insert(sequence);}}else{for(intidepth;in;i)if(!visited[i]sumnumber[i]t){visited[i]1;dfs(depth1,sumnumber[i]);visited[i]0;}}}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);while(cintn,t){for(inti1;in;i){cinnumber[i-1];text[i-1]to_string(number[i-1]);}coutSums of t:\n;solutions.clear();memset(visited,0,sizeof(visited));dfs(0,0);if(solutions.size()0)coutNONE\n;}return0;}