莫欺少年穷，修魔之旅在这开始—>算法提高课题解

剪枝与优化

1. 优化搜索顺序
2. 排除等效冗余
3. 可行性剪枝
4. 最优性剪枝
5. 记忆化搜索（dp）

思路：

1. 优化搜索顺序：木棍从小到大枚举
2. 排除等效冗余：
   (1).如果该木棍使用失败，那跟它一样长度的木棍也必定失败；
   (2).如果该木棍作为第一根但使用失败，说明它的长度大于木棒长度，则也必定失败
   (3).如果该木棍作为最后一根木棍，但后面的木棒拼凑不能成功，则该木棍也必定使用失败
3. 可行性剪枝：同一根木棍不能重复使用，拼凑的木棍之和也不能大于木棒长度
4. 注意：一根木棒必须要拼凑满才能继续拼凑下一根木棒，否则直接 return false

#include<bits/stdc++.h>

using namespace std;

const int N = 70;

int n;
int w[N];
bool st[N];
int sum,length;

//第 u 根木棒，第 u 根木棒已拼凑 s 的长度，已经枚举到第 start 根木棍
bool dfs(int u,int s,int start)
{
    if(u*length==sum) return true;

    //该木棒已经拼凑满，开始拼凑下一根木棒
    if(s==length) return dfs(u+1,0,0);

    for(int i=start;i<n;i++)
    {
        //该木棍已经用过或和大于木棒长度
        if(st[i]||s+w[i]>length) continue;

        //使用该木棍
        st[i]=true;

        //该木棍使用成功
        if(dfs(u,s+w[i],i+1)) return true;

        //该木棍使用失败
        st[i]=false;

        //该木棍大于木棒长度，或是该木棒的最后一根，但后面木棒拼凑失败
        if(!s||s+w[i]==length) return false; 

        //该木棍使用失败，跟它长度一样的木棍也肯定不行
        int j=i;
        while(j<n&&w[j]==w[i]) j++;
        i=j-1;
    }

    //该木棒已经没有木棍可以把它拼凑满
    return false;
}

int main()
{
    while(cin>>n,n)
    {
        memset(st,0,sizeof st);

        sum=0;
        for(int i=0;i<n;i++) cin>>w[i],sum+=w[i];

        //从大到小枚举
        sort(w,w+n);
        reverse(w,w+n);

        length=1;
        while(true)
        {
            //肯定是能整除的
            if(sum%length==0&&dfs(0,0,0))
            {
                cout<<length<<endl;
                break;
            }

            length++;
        }
    }

    return 0;
}