UVa 574 Sum It Up

题目描述

题目要求从给定列表中找出所有不同的子集，其和等于目标数ttt。列表中的数字按非递增顺序给出，可能有重复。输出时，每个子集中的数字按非递增顺序排列，且子集之间按字典序降序排列（即第一个数字大的优先，相同则比较第二个，依此类推）。若无解，输出NONE。

输入格式

输入包含多个测试用例，每行一个。每行第一个整数ttt，第二个整数nnn，后面nnn个整数。若n=0n = 0n=0则输入结束。t<1000t < 1000t<1000，1≤n≤121 \le n \le 121≤n≤12，每个数<100< 100<100。

输出格式

对于每个测试用例，先输出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 3+1 2+2 2+1+1 Sums of 5: NONE 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≤12n \le 12n≤12，可以使用回溯法枚举所有子集。

回溯算法

• 按顺序遍历列表，每个数字可选或不选。
• 由于数字可能有重复，使用集合solutionssolutionssolutions去重。
• 回溯时，若当前和等于ttt，则将所选数字组成的字符串加入集合。
• 若当前和大于ttt，则剪枝。

输出排序

由于列表本身是非递增顺序，且回溯按顺序选择，生成的子集自然满足降序。但需要去重后按降序输出，可以使用集合自动排序（字符串字典序降序对应数字降序）。

复杂度分析

最多212=40962^{12} = 4096212=4096种子集，可接受。

代码实现

// Sum It Up// UVa ID: 574// Verdict: Accepted// Submission Date: 2016-08-17// UVa Run Time: 0.040s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intnumber[12],visited[12],t,n,counter;string text[12];set<string>solutions;voiddfs(intdepth,intsum){if(sum==t){string sequence;boolfirst_number=true;for(inti=0;i<n;i++)if(visited[i]){if(first_number)first_number=false;elsesequence+='+';sequence+=text[i];}if(solutions.find(sequence)==solutions.end()){cout<<sequence<<'\n';solutions.insert(sequence);}}else{for(inti=depth;i<n;i++)if(!visited[i]&&sum+number[i]<=t){visited[i]=1;dfs(depth+1,sum+number[i]);visited[i]=0;}}}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);while(cin>>t>>n,t){for(inti=1;i<=n;i++){cin>>number[i-1];text[i-1]=to_string(number[i-1]);}cout<<"Sums of "<<t<<":\n";solutions.clear();memset(visited,0,sizeof(visited));dfs(0,0);if(solutions.size()==0)cout<<"NONE\n";}return0;}