经典剪枝——木棒

搜索顺序
    原始木棒的长度

节点
    （正在拼第s根原始木棒，当前拼接原始木棒长度，遍历所有可能小木棍（编号） ）

剪枝
    优化搜索顺序
        木棍长度从大到小排序，优先尝试较长的木棍
    排除等效冗余
        在当前原始木棒中
            拼接一个小木棍失败后不在尝试相同长度的木棒
            拼接第一根小木棍失败后当前分支失败
            拼接最后一根小木棍成功但是拼接剩余原始木棒失败后当前分支失败

#include<bits/stdc++.h>
using namespace std;

const int N=100;
int a[100],len,cnt,n;
bool st[100];

bool dfs(int s,int cab,int num)
{
    if(s>cnt)
        return true;

    if(cab==len)
        return dfs(s+1,0,1);

    int fail=0;             //剪枝2
    for(int i=num;i<=n;i++) //剪枝1
    {
        if(!st[i]&&cab+a[i]<=len&&a[i]!=fail)
        {
            st[i]=1;
            if(dfs(s,cab+a[i],i+1))
                return true;
            st[i]=0;

            fail=a[i];

            if(cab==0||a[i]+cab==len)
                return false;
        }
    }
    return false;
}

int main()
{
    while(cin>>n,n)
    {
        int sum=0,maxx=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            maxx=max(maxx,a[i]);
            sum+=a[i];
        }

        sort(a+1,a+1+n,greater<int>());//剪枝1

        for(len=maxx;len<=sum;len++)
        {
            if(sum%len!=0)
                continue;
            cnt=sum/len;

            memset(st,0,sizeof st);

            if(dfs(1,0,1))
                break;
        }

        cout<<len<<endl;
    }
}