搜索+剪枝
【剪枝操作】：若某组拼接不成立，且此时 已拼接的长度为0 或 当前已拼接的长度与刚才枚举的长度之和为最终枚举的答案时，则可直接跳出循环。因为此时继续枚举其它更小的值时，显然可能情况更少，且同样凑不完。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int maxn = 55;
int cnt[maxn];
int n, tot, max_x, min_x, x;
void dfs(int num, int sum, int target, int p)
{
if(num == 0){
printf("%d\n", target);
exit(0);
}
if(sum == target){
dfs(num - 1, 0, target, max_x);
}
else{
for(int i = p; i >= min_x; i--){
if(cnt[i] && i + sum <= target){
cnt[i]--;
dfs(num, sum + i, target, i);
cnt[i]++;
if(sum == 0 || sum + i == target){ /***剪枝***/
break;
}
}
}
}
}
int main()
{
scanf("%d", &n);
min_x = maxn;
for(int i = 1; i <= n; i++){
scanf("%d", &x);
if(x <= 50){
cnt[x]++;
tot += x;
min_x = min(min_x, x);
max_x = max(max_x, x);
}
}
for(int i = max_x; i <= tot; i++){
if(tot % i == 0){
dfs(tot / i, 0, i, max_x);
}
}
return 0;
}