1 #include "iostream" 2 #include "algorithm" 3 #include "memory.h" 4 using namespace std; 5  6 int sticks[64],n,len,num; 7 bool used[64]; 8  9 bool cmp(int a,int b)10 {11     return a > b;12 }13 14 bool dfs(int cur,int left,int level)15 {  //cur: 当前已经计算的木棒编号，left:该段还剩的长度，level:已经成功的木棒数16     if (left == 0) {//匹配一根木棒成功17         if (level == num-2)  return true;18         for (cur = 0; used[cur];cur++);//找到下一个未访问过的长度19         used[cur] = true;20         if (dfs(cur+1,len-sticks[cur],level+1))21             return true;22         used[cur] = false;              //回溯23         return false;24     } else {25             if (cur >= n-1) return false;26             for (int i = cur;i < n; ++ i) {//剪枝27                 if (used[i]) continue;      //访问过的长度28                 if (sticks[i] == sticks[i-1] && !used[i-1]) continue; //相等的长度已经搜过的不搜29                 if (sticks[i] > left) continue;                     //大于达到len的生育长度30                 used[i] = true;31                 if (dfs(i,left-sticks[i],level)) return true;32                 used[i] = false;        //回溯33             }34         return false;35     }36 }37 int main()38 {39     while (cin >> n,n) {40         int sum = 0;41         for (int i = 0;i < n; ++ i) {42             cin >> sticks[i];43             if(sticks[i]>50)44             {45                 n--;i--;continue;46             }47             sum += sticks[i];48         }49         sort(sticks,sticks + n,cmp);//剪枝50         bool end = false ;51         for (len = sticks[0]; len <= sum/2; len++) {52             if (sum%len == 0) {     //剪枝53                 used[0] = true;54                 num = sum/len;55                 if (dfs(0,len-sticks[0],0)) {56                     end = true;57                     cout << len << endl;58                     break;59                 }60                 used[0] = false;    //回溯61             }62         }63         if (!end) cout << sum << endl;64         memset(used,0,sizeof(used));65     }66     return 0;67 }