因为n比较小,我们可以考虑时间复杂度较大的算法,我们可以构造一个环(假设环上有m个点),环上的点满足
s
1
a
1
+
s
2
a
2
+
s
3
a
3
+
.
.
.
+
s
m
a
m
=
0
s_1a_1 + s_2a_2 + s_3a_3 + ... + s_ma_m = 0
s1a1+s2a2+s3a3+...+smam=0 (s是选的符号),我们可以枚举环的长度并枚举s可能的情况,只要有一组环的和为0,即可构造。
#include <cstdio>
#include <iostream>
#include <cstring>
int T,n,a[15];
void solve(){
memset(a,0,sizeof(a));
scanf("%d",&n);
int sum = 0,m = 1;
for(int i = 1;i <= n;i++){
scanf("%d",&a[i]);
m *= 3;
}
for(int i = 1;i < m;i++){
int k = i;
sum = 0;
for(int i = 1;i <= n;i++){
int s = k % 3;
k /= 3;
if(s == 2)s = -1;
sum += s * a[i];
}
if(sum == 0){
puts("YES");
return;
}
}
puts("NO");
}
int main(int argc,char *argv[]){
scanf("%d",&T);
while(T--)solve();
return 0;
}