在loj上做的这一题,现在dfs程序一直无法结束但又不完全像是死循环,求调
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
int n,a[61],sum,num,l,maxa,nmax;
bool vis[61];
bool cmp(int x,int y)
{
return x>y;
}
bool dfs(int i,int len,int st)
{
// cout<<i<<" "<<len<<" "<<st<<endl;
if(i>num) return 1;
if(len==l) return dfs(i+1,0,1);
for(int j=st;j<=n;j++)
{
if(vis[j]) continue;
if(len+a[j]>l) continue;
// cout<<i<<" "<<a[i]<<endl;
vis[j]=1;
if(dfs(i,len+a[j],j))
{
return 1;
}
vis[j]=0;
if(len==0) return 0;
if(len+a[j]==l) return 0;
}
return 0;
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sum+=a[i];
maxa=max(a[i],maxa);
}
for(int i=2;i*i<=n;i++)
{
if(sum%i==0)
{
nmax=sum/i;
break;
}
}
sort(a+1,a+n+1,cmp);
for(int i=nmax;i>=1;i--)
{
if(sum%i!=0)
{
continue;
}
memset(vis,0,sizeof(vis));
l=sum/i;
num=i;
// cout<<l<<" "<<num<<endl;
if(l<maxa) continue;
if(dfs(1,0,1))
{
scanf("%lld",l);
break;
}
}
return 0;
}