深搜部分和之前的POJ2362差不多，只是有几处需要额外的剪枝。
【思路】排序后从最短木棒开始搜索至木棒长总和，如果木棒长总和sum能整除当前棒长，则进入深搜。
【剪枝】先前POJ2362的剪枝部分不再重提，这里只讲额外的几处（我们称切断后的棒为木棒，切断前的棒为原棒）：
1.如果所有木棒等长，即排序后stick[0]=stick[n-1]，则直接输出棒长；
2.如果当前搜索的棒长即是棒长总和，无需进入深搜子程序，直接输出；
3.如果深搜中当前长度的木棒不能选择，则略去同一层中相同长度的木棒；
4.如果当前是重新开始组成一个原棒，即len=0时。如果可以组成原棒，则取frm时必然能返回真（因为组成原棒的顺序是无所谓的）；若选取frm时仍然无法组成，则说明不能组成原棒，直接退出深搜，返回假。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=+;
int n,sl;
int stick[MAXN];
int vis[MAXN]; int dfs(int side,int frm,int len)
{
if (==side) return ;
int last=-;
for (int i=frm;i>=;i--)
if (!vis[i] && stick[i]!=last)
{
vis[i]=;
if (sl==len+stick[i])
{
if (dfs(side-,n-,)) return ;
}
else if (sl>len+stick[i])
{
if (dfs(side,i-,len+stick[i])) return ;
}
vis[i]=;
last=stick[i];
if (len==) break;
}
return ;
} int main()
{
while (scanf("%d",&n))
{
if (==n) break;
int sum=;
for (int i=;i<n;i++)
{
scanf("%d",&stick[i]);
sum+=stick[i];
}
sort(stick,stick+n);
if (stick[]==stick[n-])
{
cout<<stick[]<<endl;
continue;
}
for (int i=stick[];i<=sum;i++)//i代表每一根木棒的长度
if (==sum%i)
{
sl=i;
memset(vis,,sizeof(vis));
if (i==sum || dfs(sum/i,n-,))
{
cout<<i<<endl;
break;
}
}
}
return ;
}