深搜的剪枝优化

#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N = 1e6 + 10,M = 2 * 1e4 + 10,inf = 0x3f3f3f3f;

int n,sum; 
int length; //单个木棍的长度
int a[110]; 
bool st[119]; //标记数组
bool dfs(int start,int cnt,int u) 
    /*
    start:
    表示开始坐标,便于我们搜索时不会搜到冗余的数,
    比如1 2 3 和 1 3 2拼成的木棍本质上相同
    cnt:
    表示当前拼成木棍的和
    u:
    表示正在拼第几根木棍
    */
{
    if(u * length == sum) return true; 
    //如果拼的几根木棍的积恰好等于总长度返回true

    if(cnt == length) return dfs(0,0,u+1);
    //当前木棍已拼成,继续下一根木棍
    for(int i = start; i < n; i++)
    {
        if(st[i]) continue; //被用过叉出去
        if(cnt + a[i] > length) continue; 
        //当前长度加上这个木棒的长度大于了单根限制长度叉出去

        st[i] = 1; //标记为已用过
        if(dfs(i+1,cnt + a[i], u)) return true; 
        //加上这个木棒后继续拼这一根
        st[i] = 0; //回溯

        if(!cnt) return false; 
        // 剪枝: 如果连第一根木棍都没放下,直接返回false
        
        if(cnt + a[i] == sum) return false;
        // 剪枝: 如果已经到了最后一根木棒还没拼成,返回false

        //剪枝: 如果这一根没有被放进当前木棍中,则后面跟这个木棒长度相等的木棒也可以跳过
        int j = i;
        while(j < n && a[j]==a[i]) j++;
        i = j - 1;
    }
    return false; //没找到返回false
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i]; //求出木棍的总长度
    }

    sort(a,a+n,greater<int>()); //从大到小排序,最优策略剪枝

    length = a[n-1]; //从最短的木棍开始找
    while (true) //类似于迭代加深,一个长度一个长度的搜索
    {
        if(sum % length == 0 && dfs(0,0,0)) 
        //能被整除才能找吧,不能整除还怎么平均分
        {
            cout<<length<<endl;
            break;
        }
        length++;
    }
    return 0;
}