3SUM Closure (Codeforces 1698C)
Tags: Others, 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: 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).

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.

Sample Inputs:
4
3
-1 0 1
5
1 -2 -2 1 -3
6
0 0 0 0 0 0
4
-1 2 -3 4

Sample Outputs:
YES
NO
YES
NO

Solution (Python):
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')

Solution (Python):
""""""
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')

Solution (Python):
test = int(input())
while test > 0:
    test -= 1
    n = int(input())
    arr = list(map(int, input().split()))
    arr.sort()
    if n == 3:
        sum = 0
        for i in arr:
            sum += i
        if sum not in arr:
            print('NO')
        else:
            print('YES')
        continue
    poss = True
    if n == 4:
        sum = 0
        for i in arr:
            sum += i
        for i in arr:
            sum -= i
            if sum not in arr:
                poss = False
            sum += i
        if poss:
            print('YES')
        else:
            print('NO')
        continue
    for i in range(1, n - 1, 1):
        if arr[i] != 0:
            poss = False
            break
    if arr[0] + arr[-1] != 0:
        if arr[0] != 0 and arr[-1] != 0:
            poss = False
    if poss:
        print('YES')
    else:
        print('NO')