经典搜索题。

考虑以下9种优化

1）按木棍长度排序，使得较大长度的木棍被较早的选出。

2）只找能够整除的木棍长度，因为不能被sum整除一定不会出整数根，自然也就不是最优解。

3）枚举木棍长度时只需从最大的木棍长度（拼出的木棍长度不会小于最大的长度也不会大于总长度）枚举至总和的二分之一。如果还没有出解那么答案一定是总和（sum/2~sum-1之间一定没有解）。

4）打的标记可以在回溯去除，不用每次memset，常数会低一点，算是一个小优化~

5）在拼的木棍根数达到所需要的ans值时，打上标记及时退出，在其他进行了dfs的地方回溯时也要及时退出。

6）在需要拼新的一根木棍时，选一个未被使用的木棍中最大的进行搜索

7）只找木棍长度不大于上一次搜索木棍长度的木棍来搜索

8）当前木棍长度不能进行拼接时，同长度的木棍也肯定不能，因此可以直接跳过

9）最重要的一点！！！（我看书上写的不如这位大佬写得好，我也想不出来更好的语言来描述，以下直接引用这位大佬的题解：Author:,洛谷题解第一篇即是）：

如果当前长棍剩余的未拼长度等于当前木棍的长度或原始长度，继续拼下去时却失败了，就直接回溯并改之前拼的木棍。有些人不太明白这个优化，这里简单说一下：

当前长棍剩余的未拼长度等于当前木棍的长度时，当前木棍明显只能自组一根长棍，但继续拼下去却失败，说明这根木棍不能自组？！这根木棍不自组就没法用上了，所以不用搜更短的木棍了，直接回溯，改之前的木棍；

当前长棍剩余的未拼长度等于原始长度时，说明这根原来的长棍还一点没拼，现在正在放入一根木棍。很明显，这根木棍还没有跟其它棍子拼接，如果现在拼下去能成功话，它肯定是能用上的，即自组或与其它还没用的木棍拼接。但继续拼下去却失败，说明现在这根木棍不能用上，无法完成拼接，所以直接回溯，改之前的木棍。

加入以上九种优化后，即使是指数级的DFS算法也可以较快的计算出结果，可见搜索程序中剪枝的重要性。

下面给出参考代码：

#pragma GCC optimize(3,"Ofast","inline")//吸口臭氧跑得更快~~~ #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int n,stick[105],sum,ans,ready,len,minn,used[105],edge;bool cmp(int a,int b)//优化1 {    return a>b;}void dfs(int num,int node,int rest){    if(num==ans){ready=1;return;}//优化5     if(rest==0)    {    	int po=0;        for(int i=1;i<=n;i++)        {            if(!used[i])            {                used[i]=1;                po=i;                break;            }        }        dfs(num+1,po,len-stick[po]);//优化6         used[po]=0;//优化4         if(ready)return;//优化5     }    for(int i=node+1;i<=n;i++)//优化7     {        if(!used[i]&&rest>=stick[i])        {            used[i]=1;            dfs(num,i,rest-stick[i]);            used[i]=0;            if(ready||rest==stick[i]||rest==len)return;//优化5和9             while(i
         
          >n;    for(int i=1;i<=n;i++)    {        int r;        cin>>r;        if(r>50)        {            i--;            n--;            continue;        }        stick[i]=r;        sum+=stick[i];        minn=max(minn,stick[i]);    }    sort(stick+1,stick+n+1,cmp);    for(int i=minn;i<=sum/2;i++)//优化3     {        if(sum%i!=0)continue;//优化2         //memset(used,0,sizeof(used));        ans=sum/i;        ready=0;        len=i;        used[1]=1;        dfs(1,1,len-stick[1]);        if(ready)        {        	cout<
          
           <