#include<bits/stdc++.h>
#define N 50
using namespace std;
int n,maxn,sum,top;
int a[N];
int nxt[N];
bool f[N];


bool asd(int x,int y){
	return x>y;
}
void init(){
	int x;
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		if(x<=50)
			a[++top]=x,sum+=a[top];
	}
	sort(a+1,a+top+1,asd);
	
	int l=n+1;
	for(int i=n;i;i--){
		nxt[i]=l;
		if(nxt[i]!=nxt[i+1])
			l=i;
	}
}
bool aa(int cnt,int l,int i,int stdl){
	/* 
	cnt	拼到第几根木棍 
	l	当前拼凑出的长度 
	i	考虑到第几根木棍 
	stdl标准木棍长度 
	*/
	printf("%d %d %d %d\n",cnt,l,i,stdl);
	if(cnt>sum/stdl)
		return 1;
	int fail=0;
	bool re;
	while(i<=n){
		if(f[i]){
			i++;
			continue;
		}
		if(a[i]==fail||l+a[i]>stdl){
			i=nxt[i];
			continue;
		}
		
		f[i]=1;
		
		if(l+a[i]==stdl)
			re=aa(cnt+1,0,1,stdl);
		else
			re=aa(cnt,l+a[i],i+1,stdl);
		
		f[i]=0;
		
		if(re)return 1;
		else{
			if(!l)return 0;
			fail=a[i];
		}
		i=nxt[i];
	}
	return 0;
}
int main(){
	init();
	
	maxn=a[1];
	for(int i=maxn;i<=(sum>>1);i++){
		if(sum%i)continue;
		//printf("%d\n",i);
		if(aa(1,0,1,i)){
			printf("%d",i);
			return 0;
		}
	}
	printf("%d",sum);
}

我的搜索会把最优解剪掉。。。

提供#8的样例，麻烦各位大佬帮忙看看

59
6 6 2 1 8 1 7 8 3 6 8 1 3 5 2 5 3 1 2 4 5 3 2 4 3 7 1 3 8 1 6 3 5 6 3 1 5 2 2 3 8 4 8 5 8 3 3 2 5 7 5 2 1 8 6 8 2 7 3

10