3SUM Closure
Contest: Codeforces Round 803 (Div. 2)
Difficulty rating: 1300
Tags: brute force, data structures

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 format:
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 format:
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).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
4
3
-1 0 1
5
1 -2 -2 1 -3
6
0 0 0 0 0 0
4
-1 2 -3 4

Example output:
YES
NO
YES
NO

Editorial:
Let's consider some array which is 3SUM-closed.
If the array has at least three positive elements, consider the largest three $$$x$$$, $$$y$$$, and $$$z$$$. Notice that $$$x+y+z$$$ is strictly larger than $$$x$$$, $$$y$$$, and $$$z$$$, which means that $$$x+y+z$$$ is not an element of the array (since $$$x$$$, $$$y$$$, $$$z$$$ were the largest elements). Therefore the array has $$$\leq 2$$$ positive elements.
Similarly, if the array has at least three negative elements, consider the smallest three $$$x$$$, $$$y$$$, and $$$z$$$. Notice that $$$x+y+z$$$ is strictly smaller than $$$x$$$, $$$y$$$, and $$$z$$$, which means that $$$x+y+z$$$ is not an element of the array (since $$$x$$$, $$$y$$$, $$$z$$$ were the smallest elements). Therefore the array has $$$\leq 2$$$ negative elements.
Finally, note that there is no point in having more than $$$2$$$ zeroes in the array, since any additional zeroes won't change the sums that can be formed. So if there are more than $$$2$$$ zeroes, we can remove them until there are exactly $$$2$$$.
It follows that the resulting array has at most $$$2 + 2 + 2 = 6$$$ elements. This is small, so we can brute force the condition in the problem in $$$\mathcal{O}(6^4)$$$ or $$$\mathcal{O}(6^3)$$$ time.
The time complexity is $$$\mathcal{O}(n + 6^4)$$$ or $$$\mathcal{O}(n + 6^3)$$$, depending on the implementation.