Sum It Up
Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t = 4, n = 6, and the list is [4, 3, 2, 2, 1, 1], then there are four different sums that equal 4: 4, 3+1, 2+2, and 2+1+1. (A number can be used within a sum as many times as it appears in the list, and a single number counts as a sum.) Your job is to solve this problem in general.
Input
The input file will contain one or more test cases, one per line. Each test case contains
t, the total, followed by
n, the number of integers in the list, followed by
n integers . If
n = 0 it signals the end of the input; otherwise,
t will be a positive integer less than 1000,
n will be an integer between 1 and 12 (inclusive), and will be positive integers less than 100. All numbers will be separated by exactly one space. The numbers in each list appear in nonincreasing order, and there may be repetitions.
Output
For each test case, first output a line containing `
Sums of ', the total, and a colon. Then output each sum, one per line; if there are no sums, output the line `
NONE'. The numbers within each sum must appear in nonincreasing order. A number may be repeated in the sum as many times as it was repeated in the original list. The sums themselves must be sorted in decreasing order based on the numbers appearing in the sum. In other words, the sums must be sorted by their first number; sums with the same first number must be sorted by their second number; sums with the same first two numbers must be sorted by their third number; and so on. Within each test case, all sums must be distinct; the same sum cannot appear twice.
Sample Input
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
0 0
Sample Output
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
想法 ： 这个题目以前出现在08年一个热身赛上，当时就没有过，然后一直放到现在，才过了的。还是想了好长时间的。
由于这个题目不能有重复的结果，所以我们把输入的数字分类，也就是说，有几个几。这样，我们再按照种类进行dfs 的时候，就不会出现重复的了，因为每个种类
每次dfs 从当前的index 走到下面，不会出现重复的情况。
再需要解决的就是求和的为题，求和很简单了，我们记录每种数有几个，从大到小，进行枚举，它的和就可以了。
再需要解决路径，就是做点改变，用一个二维的数组，记录有几个几，第一维记录几个数字，第二维记录这个数字是什么。
附代码 ：
#include <stdio.h>
#include <string.h>
int many[101], in[13], sum, n, kind[13], dif;
int path[50][2];
bool judge[100], ok;
void dfs(int index, int s, int pl)
{
int i, j;
if(s == sum){
ok = true;
bool f = false;
for(i = 0; i < pl; i++){
for(j = 0; j < path[i][0]; j++){
if(!f)f = true;
else putchar('+');
printf("%d", path[i][1]);
}
}
puts("");
}
else{
for(i = index; i < dif; i++){ // 对于种类，dfs
if(!judge[i]){
for(j = many[kind[i]]; j >= 1; j--){ // 每种由大到小，枚举所有的可能性
if(s + j * kind[i] <= sum){
judge[i] = 1; //标记走过
path[pl][0] = j; //记录有多少个这个数
path[pl][1] = kind[i]; //记录某个数字
// printf("dfs %d ge %d sum = %d\n", j, kind[i], s + kind[i]);
dfs(i, s + j * kind[i], pl + 1);
judge[i] = 0; // 回溯
}
}
}
}
}
}
int main(){
freopen("1197.in", "r", stdin);
freopen("1197.out", "w", stdout);
int i, j;
while(scanf("%d%d", &sum, &n), sum || n){
dif = 0;ok = false;
memset(many, 0, sizeof(many));
memset(in, -1, sizeof(in));
memset(kind, 0, sizeof(kind));
for(i = 1; i <= n; i++)
scanf("%d", &in[i]);
for(i = 0, j = 1; j < n; j++, i++){
if(in[i] != in[j]){
kind[dif++] = in[j]; // 提取种类
many[in[j]] = 1; //每种多少个。
}
else many[in[j]]++;
}
if(in[n] != in[n - 1]){
kind[dif++] = in[n]; //。。。最有也有一个。
many[in[n]] = 1;
}
else many[in[n]]++;
printf("Sums of %d:\n", sum);
dfs(0, 0, 0);
if(!ok)puts("NONE");
}
return 0;
}
对于dfs 的理解还是不好的。非常不好，这个题目还是想了很长时间，想象不出来进入dfs后的情况。