1 /*
2 * 这个题目第一次做还是暑假集训的时候，前天又把它翻了出来，本来是想找点手感的，不想在原先思路的基础上，竟把它做出来了而且还是0ms过得。仔细想想，对搜索又有了一点点认识。
3 题目要求将一系列的sticks重新组合，形成若干相等相等长度的木棒，且尽量使木棒长度最小，如果数据量比较小的话，就纯粹是搜索了，但题目要求的 sticks可能达到64根，如果纯粹的搜索则显然是会远远超过1000ms的，因而也就把剪枝放在了很重要的位置。从第一根stick开始，寻找下一根 stick使两者的长度小于等于木棒的长度，然后再寻找下一根stick，直到和为一根木棒的长度；然后又从一根没有被使用的stick开始进行下一根木棒的组合。概括一点说，就是一个深度优先搜索。
4 做完这个题目之后，仔细想了想，觉得之前没有做出来最主要的原因就出在回溯上，因为对于dfs最初使用的的返回类型是void，当某种情况不行，需要回溯到上一层时，我就会很急地使用return语句，这个时候并没有回溯到上一层，而是退出了函数；另外，也要告诫自己要控制好变量，就这个题目而言，开始也有地方的那个used值并没有做好处理。致使最后有时候会出现一些莫名其妙的结果，与产生错误的提示信息。也走了那条从TLE到WA，再到AC的路，但还是学到了很多东西。
5 */
6
7
8 #include <iostream>
9 #include <algorithm>
10 #include <cstring>
11 using namespace std;
12
13 int sticks[64], n, len, num;
14
15 bool used[64];
16
17 bool compare(const int &a, const int &b)
18 {
19 return a > b;
20 }
21
22 bool dfs(int cur, int left, int level)
23 { //cur: 当前已经计算的木棒编号，left:该段还剩的长度，level:已经成功的木棒数
24 if (left == 0)
25 { //匹配一根木棒成功
26 if (level == num - 2)
27 return true;
28 for (cur = 0; used[cur]; cur++);
29 used[cur] = true;
30 if (dfs(cur + 1, len - sticks[cur], level + 1))
31 return true;
32 used[cur] = false;
33 return false;
34 }
35 else
36 {
37 if (cur >= n - 1)
38 return false;
39 for (int i = cur; i < n; i++)
40 {
41 if (used[i])
42 continue;
43 if ((sticks[i] == sticks[i - 1]) && !used[i - 1])
44 continue;
45 if (sticks[i] > left)
46 continue;
47 used[i] = true;
48 if (dfs(i, left - sticks[i], level))
49 return true;
50 used[i] = false;
51 }
52 return false;
53 }
54 }
55
56 int main()
57 {
58 while (scanf("%d", &n) !=EOF)
59 {
60 if (n == 0)
61 break;
62 int sum = 0;
63
64 for (int i = 0; i < n; i++)
65 {
66 scanf("%d", &sticks[i]);
67 sum += sticks[i];
68 }
69 sort(sticks, sticks + n, compare);
70 bool end = false;
71
72 for (len = sticks[0]; len <= sum / 2; len++)
73 {
74 if (sum % len == 0)
75 {
76 used[0] = true;
77 num = sum / len;
78 if (dfs(0, len - sticks[0], 0))
79 {
80 end = true;
81 printf("%d\n", len);
82 break;
83 }
84 used[0] = false;
85 }
86 }
87 if (!end)
88 printf("%d\n", sum);
89 memset(used, 0, sizeof(used));
90 }
91
92 return 0;
93 }
94