经典搜索题。
考虑以下9种优化
1）按木棍长度排序，使得较大长度的木棍被较早的选出。
2）只找能够整除的木棍长度，因为不能被sum整除一定不会出整数根，自然也就不是最优解。
3）枚举木棍长度时只需从最大的木棍长度（拼出的木棍长度不会小于最大的长度也不会大于总长度）枚举至总和的二分之一。如果还没有出解那么答案一定是总和（sum/2~sum-1之间一定没有解）。
4）打的标记可以在回溯去除，不用每次memset，常数会低一点，算是一个小优化~
5）在拼的木棍根数达到所需要的ans值时，打上标记及时退出，在其他进行了dfs的地方回溯时也要及时退出。
6）在需要拼新的一根木棍时，选一个未被使用的木棍中最大的进行搜索
7）只找木棍长度不大于上一次搜索木棍长度的木棍来搜索
8）当前木棍长度不能进行拼接时，同长度的木棍也肯定不能，因此可以直接跳过
9）最重要的一点！！！（我看书上写的不如这位大佬写得好，我也想不出来更好的语言来描述，以下直接引用这位大佬的题解：Author:Kaori,洛谷题解第一篇即是）：
如果当前长棍剩余的未拼长度等于当前木棍的长度或原始长度，继续拼下去时却失败了，就直接回溯并改之前拼的木棍。有些人不太明白这个优化，这里简单说一下：
当前长棍剩余的未拼长度等于当前木棍的长度时，当前木棍明显只能自组一根长棍，但继续拼下去却失败，说明这根木棍不能自组？！这根木棍不自组就没法用上了，所以不用搜更短的木棍了，直接回溯，改之前的木棍；
当前长棍剩余的未拼长度等于原始长度时，说明这根原来的长棍还一点没拼，现在正在放入一根木棍。很明显，这根木棍还没有跟其它棍子拼接，如果现在拼下去能成功话，它肯定是能用上的，即自组或与其它还没用的木棍拼接。但继续拼下去却失败，说明现在这根木棍不能用上，无法完成拼接，所以直接回溯，改之前的木棍。
加入以上九种优化后，即使是指数级的DFS算法也可以较快的计算出结果，可见搜索程序中剪枝的重要性。
下面给出参考代码：
1 #pragma GCC optimize(3,"Ofast","inline")//吸口臭氧跑得更快~~~ 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 int n,stick[105],sum,ans,ready,len,minn,used[105],edge; 8 bool cmp(int a,int b)//优化1 9 { 10 return a>b; 11 } 12 void dfs(int num,int node,int rest) 13 { 14 if(num==ans){ready=1;return;}//优化5 15 if(rest==0) 16 { 17 int po=0; 18 for(int i=1;i<=n;i++) 19 { 20 if(!used[i]) 21 { 22 used[i]=1; 23 po=i; 24 break; 25 } 26 } 27 dfs(num+1,po,len-stick[po]);//优化6 28 used[po]=0;//优化4 29 if(ready)return;//优化5 30 } 31 for(int i=node+1;i<=n;i++)//优化7 32 { 33 if(!used[i]&&rest>=stick[i]) 34 { 35 used[i]=1; 36 dfs(num,i,rest-stick[i]); 37 used[i]=0; 38 if(ready||rest==stick[i]||rest==len)return;//优化5和9 39 while(i<n&&stick[i+1]==stick[i])i++;//优化8 40 if(i==n)return; 41 } 42 } 43 } 44 int main() 45 { 46 cin>>n; 47 for(int i=1;i<=n;i++) 48 { 49 int r; 50 cin>>r; 51 if(r>50) 52 { 53 i--; 54 n--; 55 continue; 56 } 57 stick[i]=r; 58 sum+=stick[i]; 59 minn=max(minn,stick[i]); 60 } 61 sort(stick+1,stick+n+1,cmp); 62 for(int i=minn;i<=sum/2;i++)//优化3 63 { 64 if(sum%i!=0)continue;//优化2 65 //memset(used,0,sizeof(used)); 66 ans=sum/i; 67 ready=0; 68 len=i; 69 used[1]=1; 70 dfs(1,1,len-stick[1]); 71 if(ready) 72 { 73 cout<<len<<endl; 74 return 0; 75 } 76 } 77 cout<<sum<<endl; 78 return 0; 79 }