[code=c]#include
#include
#include
#include
using namespace std;
int v[70];
int a[70];
int n;
int ans;
int dfs(int index, int sum)//下标和当前木棒长度的总和
{
sum += a[index];
int l=sum;
if (sum == ans)return l;//找到就返回
if (sum > ans)return l;//大了就说明选择的这根木棒不对 返回
for (int i = index + 1; i < n; i++)//将所以可以选择的木棒枚举一遍
{
if (v[i] == 0)
{
v[i] = 1;
l=dfs(i, sum);
if (l>ans)//大了就找下一个
{
v[i] = 0;
while (1)//去除与这个长度相等的木棒 因为肯定也不满足
{
if (a[i + 1] != a[i])break;
i++;
}
}
else if (l < ans) { return l; }//如果长度不够 就直接结束dfs 因为后面的木棒长度更小 永远也得不到结果
else return l;//找到了 就退出dfs
}
}
return l; //枚举完了长度还不够 退出dfs
}
bool cmp(int a, int b)
{
return a > b;
}
int main()
{
while (cin >> n)
{
if (n == 0)break;
int k=0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
k+=a[i]; //所有的和 作为结束的条件
}
sort(a, a + n, cmp);//从大到小排序
for (ans = a[0];ans<k; ans++)//结果一定不小于最长的木棒
{
bool flag = true;//判断是否找到循环退出的条件
memset(v, 0, sizeof(v));//每次没找到都要置零
for (int j = 0; j < n; j++)//把每个木棒遍历一遍是否能找到答案
{
if (v[j] == 0)
{
v[j] = 1;
if (dfs(j, 0) != ans) { flag = false; break; }//如果不对就退出这个循环 看下一个结果是否正常
}
}
if (flag == true)break;
}
cout << ans << endl;
}
return 0;
}[/code]