python/TangDou/AcWing/JianZhi/167_0.cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 65;
int a[N], n, len, sum;
bool st[N];

// len：每个木棒的长度
// u：当前正在装的木棒
// last:当前木棒已经装入的木棍长度
bool dfs(int u, int last) {
    // 如果上一个木棒填充完整，开启了新的木棒，那么，新木棒的当前木棍总长是0，同时，如果u个木棒全部装满就可以包含所有，就是找到了合适的木棒长度和木棒个数
    if (u * len == sum) return true;

    // 如果当前木棒已填满，开启下一个木棒
    if (last == len) return dfs(u + 1, 0);

    for (int i = 0; i < n; i++) {                 // 枚举每一个木棍
        if (st[i] || last + a[i] > len) continue; // 如果使过了，或者，当前木棒剩余空间不足以装入i木棍，放过

        st[i] = true;                         // 装入
        if (dfs(u, last + a[i])) return true; // 装入后，此路径的后续汇报了成功标识，则本路径就是成功的，不需要再继续搜索了
        // 注意：这里不能直接 return dfs(u,last+a[i]),原因是因为即使按现在这样的装法不能成功，但不代表着不可以尝试其它的木棍，不能直接 return
        // 这个bool和void的使用方法有一些区别，冉要仔细体会 ，也可以理解为在使用 bool dfs时，return要小心再小心，就能不犯错误
        st[i] = false; // 回溯
    }
    return false; // 如果上面的代码中未能return true,就表示进入了一条死的路径，当前len不合法 或者是 当前木棒选择的木棍不正确
}
int main() {
    while (cin >> n && n) {
        sum = 0;
        memset(st, false, sizeof st);
        for (int i = 0; i < n; i++) cin >> a[i], sum += a[i];
        // 从1~sum，由小到大逐个枚举木棒长度，这样，可以保证第一个符合条件的木棒长度是最小的
        // 在 木棒长度=len的前提下，开始向第1个木棒里装东西，目前第1个木棒内已装入的长度为0
        // 如果当前木棒长度=len的情况下，可以找到完美的装填办法，就是找到的答案
        for (len = 1; len <= sum; len++) {
            if (dfs(1, 0)) {
                printf("%d\n", len);
                break;
            }
        }
    }
    return 0;
}