C++(g++ 7.5.0) 解法, 执行用时: 8ms, 内存消耗: 468K, 提交时间: 2022-12-01 16:46:08

#include<bits/stdc++.h>
using namespace std;
int n; 
int a[101];
bool vis[101];
int sum;
bool dfs(int num,int len,int r,int x) 
{
	if(num==0&&r==0) return true;
	if(r==0&&num>0) {x=0;r=len;}
	for(int i=x;i<n;i++)
	{
		if(a[i]>r) continue;
		if(!vis[i]){
			vis[i]=1;
			if(dfs(num-1,len,r-a[i],i+1)) return true; 
			vis[i]=0;
			if(a[i]==r||r==len) break;//剪枝 
			while(a[i]==a[i+1]) i++;//剪枝 
		}
	}
	return false;
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++) {cin>>a[i];sum+=a[i];}
	sort(a,a+n);reverse(a,a+n);
	for(int i=a[0];i<=sum;i++)
	{
		memset(vis,0,sizeof vis);//每次试探 
		if(sum%i!=0) continue;
		if(dfs(n,i,i,0)) {cout<<i<<endl;break;}	
	}	
}

C++(clang++ 11.0.1) 解法, 执行用时: 8ms, 内存消耗: 512K, 提交时间: 2022-09-07 10:04:04

#include <bits/stdc++.h>

using namespace std;

int a[61], vis[61], sum, n;
bool dfs(int num,int len,int r,int j){
    if(!num&&!r) return true;
    if(!r&&num>0) j=0, r=len;
    for(int i=j;i<n;i++){
        if(a[i]<=r&&!vis[i]){
            vis[i] = 1;
            if(dfs(num-1,len,r-a[i],i+1)) return true;
            vis[i] = 0;
            if(a[i]==r||r==len) break;
            while(a[i]==a[i+1]) i++;
        }
    }return false;
}
int main() {
    cin >> n;
    for(int i=0;i<n;i++)  cin >> a[i], sum+=a[i];
    sort(a,a+n),reverse(a,a+n);
    for(int i=a[0];i<=sum;i++){
        if(!(sum%i)&&dfs(n,i,i,0)){cout << i << endl;break;}
    }
}