分享一些Y总视频中没提及的Acwing 167 木棒这题的剪枝方法，Y总的代码貌似会在一些其他网站被卡

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 70;
int w[N], sum, length, cnts;
int st[N];
int n;

bool dfs(int u, int len, int start)
{
    if(u == cnts - 1) return true; //剪枝-当前拼成cnts - 1条大木棒, 则剩余小木棒一定能拼成剩下的一条
    if(len == length) return dfs(u + 1, 0, 0);

    // 剪枝-排除等效冗余
    for(int i = start; i < n; ++i)
    {
        if(st[i]) continue;
        if(len + w[i] > length) continue;
        st[i] = true;
        if(dfs(u, len + w[i], i + 1)) return true;
        st[i] = false;

        // 剪枝-可行性剪枝-小棒在大棒第一个位置失败，则无可行解
        if(len == 0) return false;
        // 剪枝-可行性剪枝-小棒在大棒最后一个位置失败，则无可行解
        if(len + 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 = w[1]; //剪枝-大木棒长度一定大于等于最长的小木棒
        int res = sum;
        while(length <= sum / 2) //如果长度为总长一半的大木棒拼不成，则剩余小木棒也不够拼成一个长度相同的的大木棒, 则说明只有一根大木棒
        {
            cnts = sum / length;
            // 剪枝-可行性剪枝
            if(sum % length == 0 && dfs(0, 0, 0))
            {
                res = length;
                break;
            }
            ++length;
        }
        cout << res << endl;
    }
    return 0;
}