记忆步骤：
1.全局变量应该有木棍数组a和标记数组vis
主函数：
1.最小木棍长度len，标记是否有答案变量f
2.输入，并记录木棍的最大值maxx和全部长度sum
3.从大到小排序
4.遍历len从maxx到sum，如果sum刚好是len的倍数，那么证明有复原方案，进行深搜
dfs函数：
1.dfs(已经使用的木棍数量tot，当前复原木棍长度l，从第now根木棍开始)
2.如果标记f为真，结束搜索
3.如果使用木棍数量tot等于总数n并且此时木棍长度为0，证明所有木棍已经复原完毕，有结果，则标记f更新为1，结束搜索
4.记录上一次使用的长度为last等于-1，用于排除重复的复原方案
5.循环从第几根木棍开始，i从now到n
6.如果第i根木棍没有标记过，并且，当前长度l 加上 第i根木棍长度a[i] 小于等于目标木棍长度len，证明这根木棍能用
7.为了排除重复情况，先判断 l + a[i]是否等于last，如果等于那么是重复情况，则跳过
8.没有触发排重则把last记录为l + a[i]
9.标记第i根木棍
10.如果l+a[i]刚好等于len，证明刚好匹配，继续重新深搜dfs(木棍使用数量tot+1，当前长度为0，从第1根重新搜索）
11.否则说明l + a[i]还是小于len的，还要继续拼接木棍，继续从第i +1根开始搜索，dfs(木棍使用数量tot +1，当前长度则为l+a[i]，从i+1根木棍开始搜索），这里的原因是因为我们从大到小排序了，所以继续拼接木棍，只能从下一根开始
12.回溯，清空第i根木棍标记
13.剪枝：如果l刚好为0，或者 l+a[i]刚好等于目标长度len，说明此时已经是最优情况了，继续搜索是没有更好的方案的，l + a[i]等于len很好解释，都匹配成功了没必要继续匹配；l = 0，拿样例的2+2+2来举例，就会发现l = 0是回溯到了最初的时候，而此时所有的5+1情况都匹配完了，很明显也是没有继续匹配的方案，所以也要结束，不然我们继续搜索下去，遇见的木棍都是已经标记过的，所以没有必要继续搜索了
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e3+10,inf = 0x3f3f3f3f; int a[N],vis[N]; int len,n,f; void dfs(int tot,int l,int now) { if(f)return; if(tot == n && l == 0) { f = 1;return; } int last = -1; for(int i = now; i <= n; i++) { if(vis[i] == 0 && l + a[i] <= len) { if(l + a[i] == last)continue; last = l + a[i]; vis[i] = 1; if(l + a[i] == len) dfs(tot + 1,0,1); else dfs(tot + 1, l + a[i], i + 1); vis[i] = 0; if(l == 0 || l + a[i] == len)break; //没有更好的结果 } } } int main() { cin >> n; int maxx = 0,sum = 0; for(int i = 1; i <= n; i++) { cin >> a[i]; maxx = max(a[i],maxx); sum += a[i]; } sort(a + 1, a + 1 + n, greater<int>()); for(len = maxx; len <= sum; len++) if(sum % len == 0) { f = 0; dfs(0,0,1); if(f)break; } cout << len; return 0; }