//一道強搜索題
1 #include<iostream>
2 #include<algorithm>
3 #define MAXN 65
4 using namespace std;
5
6 int _m[MAXN];
7 int _sum[MAXN];
8 bool mark[MAXN];
9 bool op(int a,int b);
10 bool boo;
11 int num;
12 int sum_all;
13 void search(int len,int index,int sum,int n,int time);
14 int main()
15 {
16 //freopen("acm.acm","r",stdin);
17 int n;
18 int i;
19 int j;
20 int sum;
21 int max;
22 int time;
23 while(1)
24 {
25 scanf("%d",&n);
26 if(!n)
27 break;
28 sum_all = 0;
29 memset(mark,false,sizeof(mark));
30 memset(_m,0,sizeof(_m));
31 sum = 0;
32 for(i = 0; i < n; ++ i)
33 {
34 scanf("%d",&_m[i]);
35 sum += _m[i];
36 }
37 sort(_m,_m+n,op);
38 for(i = 0; i < n; ++ i)
39 {
40 _sum[i] = _m[i];
41 }
42 max = *max_element(_m,_m+n);
43 for(i = n-2; i >= 0; -- i)
44 {
45 _sum[i] += _sum[i+1];
46 }
47
48 for(i = max; i < sum; ++ i)
49 {
50 memset(mark,false,sizeof(mark));
51 if(i > sum/2+1)
52 continue;
53 boo = false;
54 if(sum % i != 0)
55 continue;
56 num = sum/i;
57 time = 1;
58 j = 0;
59 while(_m[j] == i)
60 {
61 mark[j] = true;
62 ++ j;
63 }
64
65 if(j == sum/i)
66 {
67 printf("%d\n",i);
68 break;
69 }
70 mark[j] = true;
71 search(i,j,_m[j],n,time+j);
72 mark[j] = false;
73 if(boo)
74 {
75 printf("%d\n",i);
76 break;
77 }
78 }
79 if(i == sum)
80 cout<<sum<<endl;
81 }
82 }
83
84 void search(int len,int index,int sum,int n,int time)
85 {
86 if(time == num)
87 {
88 boo = true;
89 }
90 if(boo)
91 return;
92 int i;
93 for(i = index+1; i < n; ++ i)
94 {
95 if(!mark[i])
96 {
97 if(!mark[i-1] && _m[i] == _m[i-1])
98 continue;
99 if(sum + _sum[i] < len)
100 {
101 break;
102 }
103 if(sum + _m[i] < len)
104 {
105 mark[i] = true;
106 search(len,i,sum+_m[i],n,time);
107 mark[i] = false;
108 if(boo)
109 return;
110 }
111 else if(sum + _m[i] == len)
112 {
113 mark[i] = true;
114 int k;
115 for(k = 0; k < n; ++ k)
116 {
117 if(!mark[k])
118 break;
119 }
120 mark[k] = true;
121 search(len,k,_m[k],n,time+1);
122 if(boo)
123 return;
124 mark[i] = false;
125 mark[k] = false;
126 break;
127 }
128 }
129 }
130 }
131
132 bool op(int a,int b)
133 {
134 return a > b ;
135 }
136
137