首页 > 代码库 > hdu 1258 Sum It Up(dfs+去重)

hdu 1258 Sum It Up(dfs+去重)

题目大意:

  给你一个总和(total)和一列(list)整数,共n个整数,要求用这些整数相加,使相加的结果等于total,找出所有不相同的拼凑方法。

  例如,total = 4,n = 6,list = [4,3,2,2,1,1]。

  有四种不同的方法使得它们相加的结果等于total(即等于4),分别为:4,3+1,2+2, 2+1+1。

  在同一种拼凑方式中,每个数字不能被重复使用,但是在list中可能存在许多相等的数字。

输入:

  输入包含许多测试用例,每个用例仅占一行。每个用例包含t(total),接下来是n,接着是用空格隔开的n个整数。如果n等于零,表示输入结束。t∈(0,1000),n∈[1, 12],list中的每个整数∈[1, 100],list中的数字是以降序排列,数字中可能出现重复的数字。

输出:

  每个测试用例,第一行输出“Sums of [total的值]:”,接下每一行输出一个结果集,如果一个结果集都没有则输出“NONE”。每个结果集要按照降序输出,并且结果集之间也要按照降序排序,结果集之间的比较从第一个数字开始,数字大的结果集大,如果第一个数字相同,则比较第二个数字,第二个数字大的,则结果集大,如果第二个数字也相同,则比较第三个数字,以此类推。不能出现相同的结果集。

解题思路:

  类似hdu 1455 Sticks,但是比1455简单的多。搞一个数组记录结果集,每次搜索到结果的时候,就输出结果集,由于list是降序的,并且数字可能在list中重复出现,因此回溯的时候记得去掉重复的结果集。

AC代码:

 1 //19475530    2017-01-02 21:07:46    Accepted    1258    0MS    1720K    1332 B    C++    潮州牛肉丸
 2 #include <stdio.h>
 3 #include <string.h>
 4 
 5 int total;            // the list that add up to total. t < 1000
 6 int n;                // list中元素个数
 7 int list[20];        // 记录数字 list[x] ∈ (0, 100)
 8 bool visit[20];     // 判重
 9 
10 int result[1010];    // 记录结果集
11 int count;            // 记录result中的元素个数
12 int flag;            // 记录是否搜索到结果,一次都没有搜索到则为false
13 
14 void init(void)
15 {
16     count = 0;
17     flag = false;
18     memset(list, 0x00, sizeof(list));
19     memset(visit, 0x00, sizeof(visit));
20 }
21 
22 // sum:当前累加和,index:上一次搜索到的下标位置
23 void dfs(int sum, int index)
24 {
25     if (total == sum)
26     {
27         // 输出结果集
28         flag = true;
29         printf("%d", result[0]);
30         for (int i = 1; i < count; ++i)
31             printf("+%d", result[i]);
32         printf("\n");
33         return;
34     }
35 
36     for (int i = index + 1; i < n; ++i)
37     {
38         if (true == visit[i])
39             continue;
40 
41         if (list[i] + sum <= total)
42         {
43             result[count++] = list[i];
44             visit[i] = true;
45             dfs(list[i] + sum, i);
46             visit[i] = false;
47             count--;
48 
49             // 关键:去掉重复的结果集
50             while (i < n && list[i] == list[i + 1]) ++i;
51         }
52     }
53     return;
54 }
55 
56 int main(void)
57 {
58     while (scanf("%d %d", &total, &n) != EOF && 0 != n)
59     {
60         init();
61         for (int i = 0; i < n; ++i)
62             scanf("%d", &list[i]);
63 
64         printf("Sums of %d:\n", total);
65         dfs(0, -1);
66         if (false == flag)
67             printf("NONE\n");
68     }
69     return 0;
70 }

 

hdu 1258 Sum It Up(dfs+去重)