You are given an array $a$ of length $n$. The array is called 3SUM-closed if for all distinct indices $i$, $j$, $k$, the sum $a_i + a_j + a_k$ is an element of the array. More formally, $a$ is 3SUM-closed if for all integers $1 \leq i < j < k \leq n$, there exists some integer $1 \leq l \leq n$ such that $a_i + a_j + a_k = a_l$.

Determine if $a$ is 3SUM-closed.


-----Input-----

The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains an integer $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the length of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \leq a_i \leq 10^9$) — the elements of the array.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output "YES" (without quotes) if $a$ is 3SUM-closed and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).


-----Examples-----

Input
4
3
-1 0 1
5
1 -2 -2 1 -3
6
0 0 0 0 0 0
4
-1 2 -3 4
Output
YES
NO
YES
NO


-----Note-----

In the first test case, there is only one triple where $i=1$, $j=2$, $k=3$. In this case, $a_1 + a_2 + a_3 = 0$, which is an element of the array ($a_2 = 0$), so the array is 3SUM-closed.

In the second test case, $a_1 + a_4 + a_5 = -1$, which is not an element of the array. Therefore, the array is not 3SUM-closed.

In the third test case, $a_i + a_j + a_k = 0$ for all distinct $i$, $j$, $k$, and $0$ is an element of the array, so the array is 3SUM-closed.

Difficulty: EASY
Tags: Data structures

Complete search
Skill types: Data structures

Complete search

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	a0 = 0
	a1 = 0
	a2 = 0
	if n == 3:
		if sum(arr) in arr:
			print('YES')
			continue
		else:
			print('NO')
			continue
	result = 'YES'
	if n == 4:
		s = sum(arr)
		for i in arr:
			if s - i not in arr:
				result = 'NO'
		print(result)
		continue
	for i in arr:
		if i > 0:
			if a1 == 0:
				a1 = i
			else:
				print('NO')
				break
		elif i < 0:
			if a2 == 0:
				a2 = i
			else:
				print('NO')
				break
	else:
		if a1 == -a2 or a1 == 0 or a2 == 0:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	nums.sort()
	if nums[-1] + nums[-2] + nums[-3] not in nums:
		print('NO')
	elif nums[0] + nums[1] + nums[2] not in nums:
		print('NO')
	elif nums[0] + nums[1] + nums[-1] not in nums:
		print('NO')
	elif nums[0] + nums[-2] + nums[-1] not in nums:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(pos, neg) = ([], [])
	has_zero = 0
	for a_i in a:
		if a_i > 0:
			pos.append(a_i)
			if len(pos) + has_zero >= 3:
				break
		elif a_i < 0:
			neg.append(a_i)
			if len(neg) + has_zero >= 3:
				break
		else:
			has_zero = 1
	else:
		S = pos + neg + ([0] if has_zero else [])
		L = len(S)
		for i in range(L):
			for j in range(i + 1, L):
				for k in range(j + 1, L):
					tot = S[i] + S[j] + S[k]
					if tot not in S:
						break
				else:
					continue
				break
			else:
				continue
			break
		else:
			print('YES')
			continue
	print('NO')


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	if n == 3:
		if sum(A) in A:
			print('YES')
		else:
			print('NO')
		continue
	if n == 4:
		if A[0] + A[1] + A[2] in A and A[0] + A[1] + A[3] in A and (A[0] + A[2] + A[3] in A) and (A[3] + A[1] + A[2] in A):
			print('YES')
			continue
	first = None
	count = 0
	for a in A:
		if a != 0:
			if not first:
				first = a
				count += 1
			elif first != -a or count == 2:
				count = 3
				break
			else:
				count += 1
	if count <= 2:
		print('YES')
	else:
		print('NO')


from collections import *
from functools import lru_cache

def readline():
	s = input()
	return s.split(' ')

def readlineint():
	return [*map(int, readline())]

def readint():
	s = input()
	return int(s)

def testcase():
	N = readint()
	t = readlineint()
	t = [*filter(bool, t)]
	if len(t) >= 5:
		print('NO')
		return
	noOf0 = N - len(t)
	if noOf0 > 2:
		noOf0 = 2
	for i in range(noOf0):
		t.append(0)
	d = defaultdict(bool)
	for k in t:
		d[k] = True
	for i in range(0, len(t)):
		for j in range(i + 1, len(t)):
			for k in range(j + 1, len(t)):
				if not d[t[i] + t[j] + t[k]]:
					print('NO')
					return
	print('YES')
N = readint()
for _ in range(N):
	testcase()


from itertools import combinations
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	c = (n - 1) * [0]
	if a[0] == a[-1] == 0:
		print('YES')
		continue
	if -a[0] == a[-1] and a[1] == a[-2] == 0:
		print('YES')
		continue
	if a[:-1] == c or a[1:] == c:
		print('YES')
		continue
	if len(a) == 3 and sum(a) in a:
		print('YES')
		continue
	if len(a) == 4:
		ans = 'YES'
		for x in combinations(a, 3):
			if sum(x) not in a:
				ans = 'NO'
				break
		print(ans)
		continue
	print('NO')


e = enumerate
for s in [*open(0)][2::2]:
	a = sorted(map(int, s.split()))
	a[3:-3] = []
	print('NYOE S'[all((x + y + z in a for (i, x) in e(a) for (j, y) in e(a[:i]) for z in a[:j]))::2])


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	B = []
	S = set(A)
	(minus, plus, zero) = (0, 0, 0)
	for i in range(n):
		if A[i] < 0:
			minus += 1
			B.append(A[i])
		if A[i] > 0:
			plus += 1
			B.append(A[i])
		if minus >= 3 or plus >= 3:
			ans.append('NO')
			return
	if 0 in S:
		B.append(0)
	m = len(B)
	for i in range(m):
		for j in range(i + 1, m):
			for k in range(j + 1, m):
				if B[i] + B[j] + B[k] not in S:
					ans.append('NO')
					return
	ans.append('YES')
	return
ans = []
for _ in range(int(input())):
	solve()
for s in ans:
	print(s)


for s in [*open(0)][2::2]:
	a = sorted(map(int, s.split()))
	print('NYOE S'[all((sum(x) in a for x in (a[:3], a[-3:], a[:2] + a[-1:], a[:1] + a[-2:])))::2])


for s in [*open(0)][2::2]:
	a = sorted(map(int, s.split()))
	print('NYOE S'[{*map(sum, (a[:i] + a[len(a) + i - 3:] for i in range(4)))} <= {*a}::2])


from os import error
import sys
input = sys.stdin.readline
DEBUG = False

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve():
	n = inp()
	datum = inlt()
	zcount = sum([1 for c in datum if c == 0])
	pos = [c for c in datum if c > 0]
	neg = [c for c in datum if c < 0]
	zcount = min(zcount, 2)
	if len(pos) > 2:
		return 'NO'
	if len(neg) > 2:
		return 'NO'
	datum = pos + neg + [0] * zcount
	n = len(datum)
	ds = set(datum)
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				if datum[i] + datum[j] + datum[k] not in ds:
					return 'NO'
	return 'YES'
q = inp()
for t in range(q):
	ans = solve()
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	vals = set(a)
	ans = 'YES'
	if n == 3:
		if a[0] + a[1] + a[2] not in vals:
			ans = 'NO'
	elif len(vals) == 2 and 0 in vals:
		x = a.count(0)
		if x == n - 1:
			ans = 'YES'
		else:
			ans = 'NO'
	elif len(vals) == 1 and 0 in vals:
		ans = 'YES'
	elif len(vals) == 3 and 0 in vals:
		x = a.count(0)
		if x == n - 2 and sum(vals) == 0:
			ans = 'YES'
		else:
			ans = 'NO'
	elif n <= 6:
		for i in range(n - 2):
			for j in range(i + 1, n - 1):
				for k in range(j + 1, n):
					if a[i] + a[k] + a[j] not in vals:
						ans = 'NO'
	else:
		ans = 'NO'
	print(ans)


for _ in range(int(input())):
	a = int(input())
	n = list(map(int, input().split()))
	n.sort()
	if a == 3:
		if n[0] + n[1] + n[2] in n:
			print('YES')
		else:
			print('NO')
	elif a == 4:
		if n[0] + n[1] + n[2] in n and n[0] + n[1] + n[3] in n and (n[0] + n[2] + n[3] in n) and (n[1] + n[2] + n[3] in n):
			print('YES')
		else:
			print('NO')
	elif n[1] == 0 and n[-2] == 0 and (n[0] + n[-1] == 0 or n[0] == 0 or n[-1] == 0):
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	B = []
	zflag = 0
	for a in A:
		if a == 0:
			if zflag == 0:
				B.append(0)
				zflag = 1
		else:
			B.append(a)
	if len(B) >= 6:
		print('NO')
		continue
	A = B
	SETA = set(A)
	n = len(A)
	flag = 1
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				if A[i] + A[j] + A[k] in SETA:
					True
				else:
					flag = 0
	if flag == 1:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	o = set(a)
	c = a.count(0)
	if n == 3:
		if sum(a) in a:
			print('YES')
		else:
			print('NO')
	elif n == 4:
		if a[0] + a[1] + a[2] in a and a[0] + a[2] + a[3] in a and (a[0] + a[1] + a[3] in a) and (a[1] + a[2] + a[3] in a):
			print('YES')
		else:
			print('NO')
	elif len(o) == 1 and a[0] == 0:
		print('YES')
	elif len(o) == 2:
		if c == n - 1:
			print('YES')
		else:
			print('NO')
	elif len(o) == 3:
		q = sorted(o)
		if c == n - 2 and q[0] + q[-1] == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


def solve():
	pos = []
	neg = []
	zero = []
	for ele in arr:
		if ele > 0:
			pos.append(ele)
		elif ele < 0:
			neg.append(ele)
		elif len(zero) < 2:
			zero.append(ele)
	if len(pos) > 2 or len(neg) > 2:
		return 'NO'
	zero = zero + pos + neg
	for i in range(len(zero)):
		for j in range(i + 1, len(zero)):
			for k in range(j + 1, len(zero)):
				if zero[i] + zero[j] + zero[k] not in zero:
					return 'NO'
	return 'YES'
T = int(input())
for t in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = solve()
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	d = []
	c = 0
	for i in w:
		if i != 0:
			d.append(i)
			if len(d) > 4:
				print('NO')
				break
		elif c == 0 and i == 0:
			c = 1
	else:
		if c == 1:
			d.append(0)
		ans = 0
		for i in range(len(d)):
			for j in range(i):
				for k in range(j):
					if d[i] + d[j] + d[k] not in d:
						ans = 1
		print('YES' if ans == 0 else 'NO')


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	(nl, pl) = ([], [])
	for i in l:
		if i > 0:
			pl.append(i)
		if i < 0:
			nl.append(i)
	if len(nl) > 2 or len(pl) > 2:
		print('NO')
		return
	cl = nl + pl
	if 0 in l:
		cl.append(0)
	n = len(cl)
	for i in range(n - 2):
		for j in range(i + 1, n - 1):
			for k in range(j + 1, n):
				ans = cl[i] + cl[j] + cl[k]
				if not any((cl[p] == ans for p in range(n))):
					print('NO')
					return
	print('YES')
for t in range(int(input())):
	solve()


x = int(input())
for i in range(x):
	y = int(input())
	z = list(map(int, input().split()))
	z.sort()
	if z[-1] + z[-2] + z[-3] not in z:
		print('NO')
	elif z[0] + z[1] + z[2] not in z:
		print('NO')
	elif z[0] + z[1] + z[-1] not in z:
		print('NO')
	elif z[0] + z[-2] + z[-1] not in z:
		print('NO')
	else:
		print('YES')


from collections import Counter

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	st = set()
	uni = 0
	for z in arr:
		if z not in st:
			st.add(z)
			uni += 1
		if uni > 4:
			return 'NO'
	freq = Counter(arr)
	s = set(arr)
	l = len(s)
	if l > 4:
		return 'NO'
	if s == set([0]):
		return 'YES'
	if 0 in s and l == 2:
		s.remove(0)
		a = list(s)[0]
		if freq[a] == 1:
			return 'YES'
		return 'NO'
	if l == 3 and 0 in s:
		sl = list(s)
		sl.sort()
		(x, y, z) = sl
		if freq[x] != 1 or freq[z] != 1:
			return 'NO'
		if x + z != 0:
			return 'NO'
		return 'YES'
	if 0 in s:
		return 'NO'
	if n > 4:
		return 'NO'
	arr.sort()
	if n == 3:
		if sum(arr) in s:
			return 'YES'
		return 'NO'
	(a, b, c, d) = arr
	if a + b + c not in s or b + c + d not in s or a + b + d not in s or (a + c + d not in s):
		return 'NO'
	return 'YES'
for _ in range(int(input())):
	print(main())


def solve(v):
	for x in v:
		if sum(v) - x not in v:
			return 0
	return 1
for _ in range(int(input())):
	n = int(input())
	v = sorted(list(map(int, input().split())))
	flag = 0
	if n == 3 and sum(v) in v or (n == 4 and solve(v)) or (n > 4 and (v.count(0) == n - 2 and v[0] == -v[-1]) or v.count(0) > n - 2):
		flag = 1
	if flag:
		print('YES')
	else:
		print('NO')


tr = int(input())
for prt in range(tr):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	if n == 3:
		if a[0] + a[1] + a[2] in a:
			print('YES')
		else:
			print('NO')
	elif n == 4:
		s = a[0] + a[1] + a[2] + a[3]
		if s - a[0] in a and s - a[1] in a and (s - a[2] in a) and (s - a[3] in a):
			print('YES')
		else:
			print('NO')
	elif a[1] == 0 and a[n - 2] == 0 and (a[0] == 0 or a[n - 1] == 0 or a[0] == -a[n - 1]):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if len(a) == 3:
		if sum(a) in a:
			print('YES')
		else:
			print('NO')
		continue
	if sum(a[-3:]) > a[-1] or sum(a[:3]) < a[0]:
		print('NO')
		continue
	b = [0, 1, -1, -2]
	f = False
	for i in range(4):
		for j in range(i + 1, 4):
			for k in range(j + 1, 4):
				(bi, bj, bk) = (b[i], b[j], b[k])
				if a[bi] + a[bj] + a[bk] in a:
					continue
				else:
					f = True
					break
	if f:
		print('NO')
	else:
		print('YES')


def sum3(nums):
	if len(nums) == 3:
		return sum(nums) in nums
	elif len(nums) == 4:
		for i in range(4):
			if sum(nums[:i] + nums[i + 1:]) not in nums:
				return False
		return True
	nums = sorted(nums)
	if nums[1] != 0:
		return False
	if nums[-2] != 0:
		return False
	if nums[0] != 0 and nums[-1] != 0 and (nums[0] != -nums[-1]):
		return False
	return True
n = int(input())
for i in range(n):
	input()
	nums = list(map(int, input().split()))
	if sum3(nums):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	num = []
	pos_count = 0
	neg_count = 0
	zero_count = 0
	fl = True
	for item in a:
		if item > 0:
			pos_count += 1
			num.append(item)
			if pos_count > 2:
				fl = False
				break
		elif item < 0:
			neg_count += 1
			num.append(item)
			if neg_count > 2:
				fl = False
				break
		else:
			zero_count += 1
	if fl:
		zero_count = min(zero_count, 2)
		num += [0] * zero_count
		for i in range(0, len(num)):
			for j in range(i + 1, len(num)):
				for k in range(j + 1, len(num)):
					if num[i] + num[j] + num[k] not in num:
						fl = False
	if fl:
		print('YES')
	else:
		print('NO')


ncase = int(input())
for case in range(1, ncase + 1):
	n = int(input())
	a = [int(s) for s in input().split(' ')]
	ans = 'NO'
	if n == 3:
		if a[0] + a[1] + a[2] in a:
			ans = 'YES'
	elif n == 4:
		if a[0] + a[1] + a[2] in a and a[1] + a[2] + a[3] in a:
			if a[0] + a[1] + a[3] in a and a[0] + a[2] + a[3] in a:
				ans = 'YES'
	else:
		a = sorted(a)
		if a[1] == 0 and a[-2] == 0:
			if a[0] + a[-1] in a:
				ans = 'YES'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	b = sorted(map(int, input().split()))
	if n - b.count(0) > 6:
		print('NO')
	else:
		a = []
		z = 0
		for e in b:
			if e != 0:
				a.append(e)
			elif z < 3:
				a.append(e)
				z += 1
		answer = 'YES'
		n = len(a)
		for i in range(n):
			for j in range(i + 1, n):
				for k in range(j + 1, n):
					if a[i] + a[j] + a[k] not in a:
						answer = 'NO'
		print(answer)


T = int(input())
while T:
	T -= 1
	N = int(input())
	arr = list(map(int, input().split()))
	if N == 3:
		if sum(arr) in arr:
			print('YES')
		else:
			print('NO')
		continue
	pos = 0
	neg = 0
	zero = 0
	ans = 'YES'
	store = []
	for ele in arr:
		if ele == 0:
			zero += 1
			continue
		if ele > 0 and pos > 1:
			ans = 'NO'
			break
		if ele > 0:
			pos += 1
			store.append(ele)
		if ele < 0 and neg > 1:
			ans = 'NO'
			break
		if ele < 0:
			neg += 1
			store.append(ele)
	if ans == 'NO':
		print('NO')
		continue
	else:
		if pos == 0 and neg == 0:
			print('YES')
			continue
		if pos >= 2 and zero > 0 or (neg >= 2 and zero > 0):
			print('NO')
			continue
		if pos == 1 and neg == 0 or (neg == 1 and pos == 0):
			print('YES')
			continue
		store.sort()
		if pos == 1 and neg == 1 and (store[0] == -store[-1]):
			print('YES')
			continue
		elif len(store) == 3:
			if sum(store) in store:
				print('YES')
			else:
				print('NO')
			continue
		elif len(store) == 4:
			ans = 'YES'
			for (i, j, k) in [(0, 1, 2), (0, 1, 3), (1, 2, 3), (0, 2, 3)]:
				if store[i] + store[j] + store[k] not in store:
					ans = 'NO'
					break
			print(ans)
		else:
			print('NO')


e = enumerate
for s in [*open(0)][2::2]:
	a = (x, y, z, *_) = (*_, u, v, w) = sorted(map(int, s.split()))
	f = x & y & z | -u & -v & -w >= 0
	a = [*filter(None, a)] + [0] * (0 in a)
	f = f and all((x + y + z in a for (i, x) in e(a) for (j, y) in e(a[:i]) for z in a[:j]))
	print('NYOE S'[f::2])


def main():
	n = int(input())
	a = [*map(int, input().split())]
	a.sort()
	ans = True
	oCount = a.count(0)
	if a[2 if oCount == 0 else 1] < 0:
		return 'NO'
	if a[-3 if oCount == 0 else -2] > 0:
		return 'NO'
	if oCount > 2:
		a = a[:a.index(0) + 2] + a[a.index(0) + oCount:]
		n -= oCount - 2
	for i in range(n):
		for j in range(n):
			if j != i:
				for k in range(n):
					if k != j and k != i and (a[i] + a[j] + a[k] not in a):
						ans = False
	return 'YES' if ans else 'NO'
for _ in range(int(input())):
	print(main())


t = int(input())

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	pos = []
	neg = []
	zero = []
	for i in a:
		if i > 0:
			pos.append(i)
		elif i < 0:
			neg.append(i)
		elif i == 0 and len(zero) < 2:
			zero.append(i)
	if len(pos) > 2 or len(neg) > 2:
		print('NO')
		return
	_a = pos + neg + zero
	for i in range(len(_a)):
		for j in range(i + 1, len(_a)):
			for k in range(j + 1, len(_a)):
				ok = False
				for l in range(len(_a)):
					if _a[i] + _a[j] + _a[k] == _a[l]:
						ok = True
				if not ok:
					print('NO')
					return
	print('YES')
for i in range(t):
	solve()


def solve(arr, n):
	new_arr = []
	pos_c = 0
	neg_c = 0
	zero_c = 0
	for i in range(n):
		if arr[i] > 0:
			new_arr.append(arr[i])
			pos_c += 1
		elif arr[i] < 0:
			new_arr.append(arr[i])
			neg_c += 1
		elif zero_c < 2:
			new_arr.append(arr[i])
			zero_c += 1
		if pos_c > 2 or neg_c > 2:
			return 'NO'
	n = len(new_arr)
	s = set(new_arr)
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				if new_arr[i] + new_arr[j] + new_arr[k] not in s:
					return 'NO'
	return 'YES'

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		s = input().split()
		arr = list(map(int, s))
		res = solve(arr, n)
		print(res)
main()


def soln():
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	if a.count(0) >= 2:
		l.append(0)
		l.append(0)
	else:
		for i in range(a.count(0)):
			l.append(0)
	(neg, pos) = (0, 0)
	for i in a:
		if neg > 2 or pos > 2:
			print('NO')
			return
		if i < 0:
			l.append(i)
			neg += 1
		elif i > 0:
			l.append(i)
			pos += 1
	for i in range(len(l)):
		for j in range(i + 1, len(l)):
			for k in range(j + 1, len(l)):
				if l[i] + l[j] + l[k] not in l:
					print('NO')
					return
	print('YES')
for _ in range(int(input())):
	soln()


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	d = {}
	c = 0
	z = []
	ki = 0
	for x in a:
		if x == 0:
			c += 1
		else:
			z.append(x)
			ki += 1
			d[x] = 1
			if ki > 4:
				break
	if ki > 4:
		print('NO')
		continue
	if c > 0:
		d[0] = 1
		z.append(0)
	f = 1
	for i in range(len(z)):
		for j in range(i + 1, len(z)):
			for k in range(j + 1, len(z)):
				if z[i] + z[j] + z[k] not in d:
					f = 0
					break
	if f == 0:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	result = sum(a)
	flag = 0
	if a.count(0) >= n - 1:
		print('YES')
	elif n == 3:
		if sum(a) in a:
			print('YES')
		else:
			print('NO')
	elif n == 4:
		for i in range(n):
			if result - a[i] not in a:
				flag = 1
		if flag:
			print('NO')
		else:
			print('YES')
	elif a[0] < 0 and a[1] == 0 and (a[-2] == 0) and (a[-1] > 0) and (a[0] + a[-1] == 0):
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	input()
	s = list(map(int, input().split()))
	o = 0
	oo = []
	p = 0
	pp = []
	n = 0
	for k in s:
		if k > 0:
			p += 1
			pp.append(k)
		elif k < 0:
			o += 1
			oo.append(k)
		else:
			n += 1
		if o > 2 or p > 2:
			print('NO')
			break
	else:
		if p == 0 and o == 0 or p + o == 1:
			print('YES')
		elif p + o == 3 and n == 0 and (sum(oo + pp) in oo + pp):
			print('YES')
		elif p + o == 4 and n == 0 and (sum(oo + [pp[0]]) in oo + pp) and (sum(oo + [pp[1]]) in oo + pp) and (sum([oo[0]] + pp) in oo + pp) and (sum([oo[1]] + pp) in oo + pp):
			print('YES')
		elif n > 0 and p == 1 and (o == 1) and (oo[0] + pp[0] == 0):
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	p = []
	n = []
	if len(a) == 3:
		sum = a[0] + a[1] + a[2]
		if sum in a:
			print('YES')
		else:
			print('NO')
	elif len(a) == 4:
		sum = 0
		k = 0
		for i in a:
			sum += i
		s = set(a)
		for i in a:
			if sum - i not in s:
				k = 1
				break
		if k == 1:
			print('NO')
		else:
			print('YES')
	else:
		for i in a:
			if i < 0:
				n.append(i)
			elif i > 0:
				p.append(i)
		if len(p) >= 2 or len(n) >= 2:
			print('NO')
		elif len(p) == 1 and len(n) == 1 and (p[0] == abs(n[0])):
			print('YES')
		elif len(p) == 1 and len(n) == 1 and (p[0] != abs(n[0])):
			print('NO')
		elif len(p) <= 1 or len(n) <= 1:
			print('YES')
		else:
			print('NO')


from itertools import combinations
for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split(' ')))
	if sum([i > 0 for i in array]) >= 3 or sum([i < 0 for i in array]) >= 3:
		print('NO')
	else:
		array = [a for a in array if a != 0] + [0] * min(array.count(0), 3)
		s = set(array)
		for (a, b, c) in combinations(array, 3):
			if a + b + c not in s:
				print('NO')
				break
		else:
			print('YES')


for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	positive = [x for x in a if x > 0]
	negative = [x for x in a if x < 0]
	if len(positive) > 2 or len(negative) > 2:
		print('NO')
		continue
	ans = True
	nonzero = positive + negative
	if len(nonzero) < n:
		for i in range(len(nonzero)):
			for j in range(i + 1, len(nonzero)):
				sum_ = nonzero[i] + nonzero[j]
				if sum_ != 0 and sum_ not in nonzero:
					ans = False
	for i in range(len(nonzero)):
		for j in range(i + 1, len(nonzero)):
			for k in range(j + 1, len(nonzero)):
				sum_ = nonzero[i] + nonzero[j] + nonzero[k]
				if (sum_ != 0 or len(nonzero) == n) and sum_ not in nonzero:
					ans = False
	print('YES' if ans else 'NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	t = []
	c = 0
	for i in l:
		if i == 0:
			if c > 3:
				continue
			else:
				c += 1
				t.append(0)
		else:
			t.append(i)
	l = t
	n = len(l)
	if n >= 10:
		print('NO')
	else:
		ans = 'YES'
		for i in range(n):
			for j in range(i + 1, n):
				for k in range(j + 1, n):
					if l[i] + l[j] + l[k] not in l:
						ans = 'NO'
		print(ans)


def meow(l, n):
	l.sort()
	if n > 4:
		if l[0] + l[n - 1] == 0:
			i = 1
			while i < n - 1:
				if l[i] == 0:
					pass
				else:
					return False
				i = i + 1
			return True
		elif l[0] == 0 or l[n - 1] == 0:
			i = 1
			while i < n - 1:
				if l[i] == 0:
					pass
				else:
					return False
				i = i + 1
			return True
		else:
			return False
	elif n == 4:
		if l[0] + l[1] + l[2] in l and l[0] + l[1] + l[3] in l and (l[1] + l[2] + l[3] in l) and (l[0] + l[3] + l[2] in l):
			return True
		else:
			return False
	elif l[0] + l[1] + l[2] in l:
		return True
	else:
		return False
tt = 0
t = int(input())
while tt < t:
	n = int(input())
	l = list(map(int, input().split()))
	if meow(l, n):
		print('YES')
	else:
		print('NO')
	tt = tt + 1


def nfind(a, b, c, list):
	if a + b + c in list:
		return 0
	else:
		return 1
for p in range(int(input())):
	n = int(input())
	(a, x, y, z) = (list(map(int, input().split())), 0, 0, 0)
	for i in a:
		if i > 0:
			x += 1
		elif i < 0:
			y += 1
		else:
			z += 1
	if x > 2 or y > 2:
		print('NO')
	elif z == n:
		print('YES')
	else:
		(v, l, f) = (x + y, [], 0)
		for i in a:
			if i != 0:
				l.append(i)
		if v <= 2:
			for i in range(3 - v):
				l.append(0)
		elif z > 0:
			l.append(0)
		for i in range(len(l)):
			for j in range(i):
				for k in range(j):
					if nfind(l[i], l[j], l[k], l):
						f = 1
						break
		if f:
			print('NO')
		else:
			print('YES')


T = int(input())
q = []
for i in range(T):
	n = int(input())
	data = [int(i) for i in input().split()]
	q.append((n, data))

def solve(n, data):
	new_data = []
	zeros = 0
	for d in data:
		if d != 0:
			new_data.append(d)
		else:
			zeros += 1
	if len(new_data) > 4:
		print('NO')
	elif len(new_data) == 4:
		if zeros != 0:
			print('NO')
			return
		sums = sum(new_data)
		for i in range(4):
			if sums - new_data[i] not in new_data:
				print('NO')
				return
		print('YES')
	elif len(new_data) == 3:
		sums = sum(new_data)
		if sums not in new_data or zeros != 0:
			print('NO')
		else:
			print('YES')
	elif len(new_data) == 2:
		if sum(new_data) == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')
for (n, data) in q:
	solve(n, data)


def check(s, a):
	p = set(s)
	m = {}
	check = 0
	for i in s:
		if i == 0:
			check += 1
	if a == check or a - 1 == check or (check == a - 2 and sum(s) == 0):
		return 'YES'
	elif a > 10:
		return 'NO'
	else:
		l = 1
		for i in range(a):
			for j in range(i + 1, a):
				for k in range(j + 1, a):
					if s[i] + s[j] + s[k] not in p:
						l = 0
						break
		if l:
			return 'YES'
		else:
			return 'NO'
t = int(input())
while t:
	a = int(input())
	s = list(map(int, input().split()))
	print(check(s, a))
	t -= 1


num_cases = int(input())
cases = []
for i in range(num_cases):
	arr_len = input()
	inputs = list(map(int, input().split()))
	cases.append(inputs)
for ip in cases:
	pos = 0
	neg = 0
	zero = 0
	for num in ip:
		if num > 0:
			pos += 1
		elif num < 0:
			neg += 1
		else:
			zero += 1
	if pos >= 3 or neg >= 3:
		ans = 'NO'
	elif zero >= 1 and pos >= 2 or (zero >= 1 and neg >= 2):
		ans = 'NO'
	elif zero == 1:
		if pos == 1 and neg == 1:
			if sum(ip) == 0:
				ans = 'YES'
			else:
				ans = 'NO'
		else:
			ans = 'NO'
	elif zero > 1:
		if pos > 1 or neg > 1:
			ans = 'NO'
		if pos == 1 and neg == 1:
			if sum(ip) == 0:
				ans = 'YES'
			else:
				ans = 'NO'
		else:
			ans = 'YES'
	elif zero == 0:
		ans = 'YES'
		ip_set = set(ip)
		for i in range(len(ip)):
			for j in range(i + 1, len(ip)):
				for k in range(j + 1, len(ip)):
					search = ip[i] + ip[j] + ip[k]
					if search not in ip_set:
						ans = 'NO'
						break
				if ans == 'NO':
					break
			if ans == 'NO':
				break
	print(ans)


t = int(input())
for _ in range(t):
	(n,) = map(int, input().split())
	a = list(map(int, input().split()))
	if n == 3:
		if sum(a) in a:
			print('YES')
			continue
		else:
			print('NO')
			continue
	if n <= 5:
		f = True
		for i in range(n - 2):
			for j in range(i + 1, n - 1):
				for k in range(j + 1, n):
					if a[i] + a[j] + a[k] not in a:
						f = False
						break
				if not f:
					break
			if not f:
				break
		if f:
			print('YES')
			continue
		else:
			print('NO')
			continue
	a.sort()
	if (a[0] == 0 or a[-1] == 0 or a[0] == -a[-1]) and a[1] == 0 and (a[-2] == 0):
		print('YES')
		continue
	else:
		print('NO')
		continue


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	if n > 3:
		cnt1 = cnt2 = cnt3 = 0
		for i in range(n):
			if arr[i] > 0:
				cnt1 += 1
			elif arr[i] < 0:
				cnt2 += 1
			else:
				cnt3 += 1
		if cnt1 >= 3 or cnt2 >= 3:
			return 'NO'
		elif cnt3 > 0:
			return 'YES' if cnt1 <= 1 and cnt2 <= 1 and (sum(arr) in arr) else 'NO'
		elif n > 4:
			return 'NO'
		else:
			for i in range(n):
				for j in range(i + 1, n):
					for k in range(j + 1, n):
						if arr[i] + arr[j] + arr[k] in arr:
							continue
						else:
							return 'NO'
			return 'YES'
	else:
		return 'YES' if sum(arr) in arr else 'NO'
for _ in range(int(input())):
	print(solve())


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	a = sorted(a)
	MySet = set(a)
	ans = 'YES'
	if n <= 4:
		for i in range(n - 2):
			for j in range(i + 1, n - 1):
				for q in range(j + 1, n):
					if a[i] + a[j] + a[q] not in MySet:
						ans = 'NO'
	else:
		ans = 'NO'
		cnt1 = a.count(a[0])
		cnt2 = a.count(a[-1])
		cnt3 = a.count(0)
		if MySet == {0}:
			ans = 'YES'
		if len(MySet) == 2:
			if 0 in MySet and cnt3 == n - 1:
				ans = 'YES'
		if len(MySet) == 3:
			if 0 in MySet and a[0] + a[-1] == 0 and (cnt1 == 1) and (cnt2 == 1):
				ans = 'YES'
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = True
	d = {}
	(c, c1, c0) = (0, 0, 0)
	for ele in arr:
		if ele == 0:
			c0 += 1
		elif ele > 0:
			c1 += 1
		else:
			c += 1
	if c > 2 or c1 > 2:
		ans = False
	elif (c == 2 or c1 == 2) and c0 != 0:
		ans = False
	else:
		ar = []
		for ele in arr:
			if ele != 0:
				ar.append(ele)
		for i in range(min(2, c0)):
			ar.append(0)
		for ele in ar:
			d[ele] = d.get(ele, 0) + 1
		n = len(ar)
		for i in range(n):
			for j in range(i + 1, n):
				for k in range(j + 1, n):
					tm = ar[i] + ar[j] + ar[k]
					if d.get(tm, -1) == -1:
						ans = False
						break
				if ans == False:
					break
			if ans == False:
				break
	if ans:
		print('YES')
	else:
		print('NO')


def main():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if n == 3 and sum(a) in a:
		print('YES')
		return
	if n == 4:
		if a[0] + a[1] + a[2] in a and a[0] + a[1] + a[3] in a and (a[0] + a[2] + a[3] in a) and (a[1] + a[2] + a[3] in a):
			print('YES')
			return
	if a[0] < 0 and a[1] == 0 and (a[-1] > 0) and (a[-2] == 0) and (a[0] + a[-1] in a):
		print('YES')
		return
	if a.count(0) >= n - 1:
		print('YES')
		return
	print('NO')
for _ in range(int(input())):
	main()


def solve(li, n):
	(z, p, n) = (0, [], [])
	for it in li:
		if it == 0:
			z += 1
		elif it > 0:
			p.append(it)
		else:
			n.append(it)
	(pl, nl) = (len(p), len(n))
	if z:
		if pl + nl <= 1:
			return 'YES'
		if pl + nl == 2 and pl == nl and (p[0] + n[0] == 0):
			return 'YES'
		return 'NO'
	else:
		al = [*p, *n]
		L = len(al)
		if L >= 5:
			return 'NO'
		for i in range(L):
			for j in range(i + 1, L):
				for k in range(j + 1, L):
					sm = al[i] + al[j] + al[k]
					if sm not in al:
						return 'NO'
		return 'YES'
for case in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	print(solve(li, n))


from collections import *

def main():
	for t in range(int(input())):
		n = int(input())
		a = sorted(list(map(int, input().split())))
		c = Counter(a)
		if c[a[0] + a[1] + a[2]] == 0 or c[a[-1] + a[-2] + a[-3]] == 0:
			print('NO')
			continue
		b = []
		for i in range(n):
			if a[i] != 0:
				b.append(a[i])
		for i in range(min(2, n - len(b))):
			b.append(0)
		flag = True
		for i in range(len(b)):
			for j in range(i + 1, len(b)):
				for k in range(j + 1, len(b)):
					if c[b[i] + b[j] + b[k]] == 0:
						flag = False
						break
		print('YES' if flag else 'NO')
main()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	ai = list(map(int, input().split()))
	pos = list(filter(lambda x: x > 0, ai))
	neg = list(filter(lambda x: x < 0, ai))
	if len(pos) > 2 or len(neg) > 2:
		print('NO')
	else:
		arr = []
		arr += pos
		arr += neg
		if 0 in ai:
			arr.append(0)
		a = 'YES'
		for i in range(0, len(arr) - 2):
			for j in range(i + 1, len(arr) - 1):
				for k in range(j + 1, len(arr)):
					if arr[i] + arr[j] + arr[k] not in arr:
						a = 'NO'
		print(a)


def bin(arr, x):
	low = 0
	high = len(arr) - 1
	mid = 0
	while low <= high:
		mid = (high + low) // 2
		if arr[mid] < x:
			low = mid + 1
		elif arr[mid] > x:
			high = mid - 1
		else:
			return mid
	return -1

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	s = [0] * 2
	d = []
	for i in range(0, n):
		if l[i] < 0:
			s[0] += 1
			d.append(l[i])
		elif l[i] > 0:
			s[1] += 1
			d.append(l[i])
		if s[0] > 2 or s[1] > 2:
			print('NO')
			return
	if s[0] + s[1] < n:
		d.append(0)
	c = len(d)
	d.sort()
	for i in range(c):
		for j in range(i + 1, c):
			for k in range(j + 1, c):
				if bin(d, d[i] + d[j] + d[k]) == -1:
					print('NO')
					return 0
	print('YES')
T = int(input())
for t in range(T):
	solve()


from sys import stdin
import math

def main():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ans = 'NO'
	cnt1 = 0
	cnt2 = 0
	for i in range(n):
		if a[i] > 0:
			cnt1 += 1
		elif a[i] < 0:
			cnt2 += 1
	if 0 in a:
		if cnt1 <= 1 and cnt2 <= 1:
			b = []
			for i in range(n):
				if a[i] != 0:
					b.append(a[i])
			if len(b) < 2 or b[0] + b[1] == 0:
				ans = 'YES'
	elif cnt1 <= 2 and cnt2 <= 2:
		flg = 1
		for i in range(n):
			for j in range(i + 1, n):
				for k in range(j + 1, n):
					if a[i] + a[j] + a[k] not in a:
						flg = 0
		if flg == 1:
			ans = 'YES'
	print(ans)
for i in range(int(input())):
	main()


def check(n, arr):
	d = {}
	for i in arr:
		d[i] = d.get(i, 0) + 1
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				if d.get(arr[i] + arr[j] + arr[k], 0) == 0:
					return 'NO'
	return 'YES'
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(p, ne, z) = ([], [], 0)
	for i in arr:
		if i > 0:
			p.append(i)
		elif i < 0:
			ne.append(i)
		else:
			z += 1
	if len(p) >= 3 or len(ne) >= 3:
		print('NO')
	elif z:
		if len(ne) == 0 and len(p) == 0:
			print('YES')
		elif len(ne) == 1 and len(p) == 0:
			print('YES')
		elif len(p) == 1 and len(ne) == 0:
			print('YES')
		elif len(ne) == 1 and len(p) == 1 and (p[0] + ne[0] == 0):
			print('YES')
		else:
			print('NO')
	else:
		print(check(n, arr))


t = int(input())

def solve():
	n = int(input())
	lst = list(map(int, input().split()))
	arr = []
	number_0 = 0
	for i in range(n):
		if lst[i] == 0:
			if number_0 <= 2:
				number_0 += 1
				arr += [0]
		else:
			arr += [lst[i]]
	if len(arr) > 6:
		print('NO')
	else:
		for i in range(len(arr)):
			for j in range(i + 1, len(arr)):
				for k in range(j + 1, len(arr)):
					if arr[i] + arr[j] + arr[k] not in arr:
						print('NO')
						return
		print('YES')
while t:
	solve()
	t -= 1


from math import ceil
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(p, n, z) = (0, 0, 0)
	for i in a:
		if i > 0:
			p += 1
		elif i < 0:
			n += 1
		else:
			z = 1
	if p > 2 or n > 2:
		print('NO')
	else:
		ans = 'YES'
		a = [i for i in a if i != 0]
		if z:
			a.append(0)
		n = len(a)
		for i in range(n):
			for j in range(i + 1, n):
				for k in range(j + 1, n):
					if a[i] + a[j] + a[k] not in a:
						ans = 'NO'
						break
		print(ans)


import sys
input = lambda : sys.stdin.readline().strip()
t = int(input())
for _ in range(t):
	n = int(input())
	lis = list(map(int, input().split()))
	lis.sort()
	sussies = []
	for i in range(len(lis)):
		if i <= 2 or n - 3 <= i:
			sussies.append(lis[i])
	nn = len(sussies)
	sus = set(lis)
	realsus = False
	for i in range(nn):
		for j in range(i + 1, nn):
			for k in range(j + 1, nn):
				if sussies[i] + sussies[j] + sussies[k] not in sus:
					realsus = True
	if not realsus:
		print('YES')
	else:
		print('NO')


t = int(input())
for vvod in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	nz = list()
	c = 0
	for i in a:
		if i != 0:
			nz.append(i)
	if len(nz) <= 1:
		print('YES')
	elif len(nz) == 2:
		if nz[0] + nz[1] == 0:
			print('YES')
		else:
			print('NO')
	elif len(nz) == 3:
		if n > 3:
			print('NO')
		else:
			zaz = 0
			for i in nz:
				zaz += i
			if zaz in nz:
				print('YES')
			else:
				print('NO')
	elif len(nz) == 4:
		if n > 4:
			print('NO')
		else:
			for i in range(len(nz)):
				zaz = 0
				for j in range(len(nz)):
					if j != i:
						zaz += nz[j]
				if zaz not in nz:
					c = 1
					break
			if c == 1:
				print('NO')
			else:
				print('YES')
	else:
		print('NO')


t = int(input())
r = []
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = n = z = 0
	b = []
	broken = False
	for e in a:
		if e > 0:
			p += 1
		if e < 0:
			n += 1
		if e == 0 and z == 0:
			z += 1
			b.append(0)
		if p >= 3 or n >= 3:
			r.append('NO')
			broken = True
			break
		if e != 0:
			b.append(e)
	if not broken:
		l = len(b)
		s = set(b)
		flag = False
		for i in range(l):
			for j in range(i + 1, l):
				for k in range(j + 1, l):
					if b[i] + b[j] + b[k] not in s:
						flag = True
						r.append('NO')
						break
				if flag:
					break
			if flag:
				break
		if not flag:
			r.append('YES')
for e in r:
	print(e)