DFS题，优化比较麻烦。首先要把棍子从大大小排序下，因为大棍子拼不成的概率大于小棍子拼不成的概率。主要有两个优化：
1.当当前棍子是某一跟整个棍子的开始时，如果搜不到结果，那么就不要再搜了。因为：开头的棍子限制最小，并且它总要作为某一根整个棍子的一部分。
2.当当前棍子和前面的棍子长度相等，并且前面那根没用过。直接跳过。（这个优化主要是对坑爹数据进行的，主要还是第一个优化。）。
别的优化基本都是浮云。欢迎喷子，欢迎指点。
#include <cstdio>
#include <cstdlib>
#include <cstring>
int stick[110];
int flag[110];
int scount;
int find;
int cmp(const void* a,const void* b)
{
return *(int*)b - *(int*)a;
}
int testdata = 0;
void dfs(int start,int len,int N,int count)
{
testdata++;
int i,j;
if( (len == 0 && count == 0) || find == 1)
{
find = 1;
return;
}
if(len == 0)
{
i =0;
while(flag[i] == 1)
i++;
flag[i] = 1;
if(stick[i] != N)
dfs(i+1,stick[i],N,count);
else
dfs(0,0,N,count-1);
flag[i] = 0;
return;
}
for(i=start;i<scount;i++)
{
if(i && !flag[i-1] && !flag[i] && stick[i] == stick[i-1])
continue;
if(!flag[i])
{
if(len+stick[i] < N)
{
flag[i] = 1;
dfs(i+1,len+stick[i],N,count);
flag[i] = 0;
}
else if(len+stick[i] == N)
{
flag[i] = 1;
dfs(0,0,N,count-1);
flag[i] = 0;
break;
}
}
}
}
int main()
{
int i;
int total;
while(scanf("%d",&scount)!=EOF && scount)
{
int minstart = 0;
total = 0;
for(i=0;i<scount;i++)
{
scanf("%d",&stick[i]);
total += stick[i];
}
qsort(stick,scount,sizeof(int),cmp);
minstart = stick[0];
find = 0;
for(i=minstart;;i++)
{
if(total%i == 0)
{
memset(flag,0,sizeof(flag));
dfs(0,0,i,total/i);
//printf("dfs(0.0.%d.%d)\n",i,total/i);
//printf("total::%d\n",total);
//printf("testdata::%d\n",testdata);
//printf("%d\n",i);
if(find == 1)
{
printf("%d\n",i);
break;
}
}
}
}
return 0;
}