时间复杂度太高,求大佬指点qwq
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
bool ans1;
int m,vis[50];
int sum=0;
bool ans[11];
int w[21];
bool cmp(int a,int b)
{
return a>b;
}
void dfs(int step,int a,int b,int c,int d)
{
if(a>sum/4||b>sum/4||c>sum/4||d>sum/4)return;
if(step==m+1)
{
if(a==b&&b==c&&c==d)ans1=true;
return;
}
for(int i=1;i<=m;i++)
{
if(vis[i]==0)
{
vis[i]=1;
dfs(step+1,a+w[i],b,c,d);
dfs(step+1,a,b+w[i],c,d);
dfs(step+1,a,b,c+w[i],d);
dfs(step+1,a,b,c,d+w[i]);
vis[i]=0;
}
}
}
int main() {
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>m;
for(int j=1;j<=m;j++)
{
cin>>w[j];
sum+=w[j];
}
sort(w+1,w+n+1,cmp);
if(sum%4==0)
{
dfs(1,0,0,0,0);
ans[i]=ans1;
ans1=false;
}
sum=0;
}
for(int i=1;i<=n;i++)
{
if(ans[i]==true)cout<<"yes\n";
else cout<<"no\n";
}
return 0;
}