Array Differentiation (Codeforces 1552D)
Tags: Math, bitmasks

You are given a sequence of $$$n$$$ integers $$$a_1, \, a_2, \, \dots, \, a_n$$$.Does there exist a sequence of $$$n$$$ integers $$$b_1, \, b_2, \, \dots, \, b_n$$$ such that the following property holds?  For each $$$1 \le i \le n$$$, there exist two (not necessarily distinct) indices $$$j$$$ and $$$k$$$ ($$$1 \le j, \, k \le n$$$) such that $$$a_i = b_j - b_k$$$. 

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 20$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10$$$).The second line of each test case contains the $$$n$$$ integers $$$a_1, \, \dots, \, a_n$$$ ($$$-10^5 \le a_i \le 10^5$$$).

Output: For each test case, output a line containing YES if a sequence $$$b_1, \, \dots, \, b_n$$$ satisfying the required property exists, and NO otherwise.

Note: In the first test case, the sequence $$$b = [-9, \, 2, \, 1, \, 3, \, -2]$$$ satisfies the property. Indeed, the following holds:   $$$a_1 = 4 = 2 - (-2) = b_2 - b_5$$$;  $$$a_2 = -7 = -9 - (-2) = b_1 - b_5$$$;  $$$a_3 = -1 = 1 - 2 = b_3 - b_2$$$;  $$$a_4 = 5 = 3 - (-2) = b_4 - b_5$$$;  $$$a_5 = 10 = 1 - (-9) = b_3 - b_1$$$. In the second test case, it is sufficient to choose $$$b = [0]$$$, since $$$a_1 = 0 = 0 - 0 = b_1 - b_1$$$.In the third test case, it is possible to show that no sequence $$$b$$$ of length $$$3$$$ satisfies the property.

Sample Inputs:
5
5
4 -7 -1 5 10
1
0
3
1 10 100
4
-3 2 10 2
9
25 -171 250 174 152 242 100 -205 -258

Sample Outputs:
YES
YES
NO
YES
YES

Solution (Python):
from itertools import *
for s in [*open(0)][2::2]:
    a = (*map(int, s.split()),)
    n = len(a)
    print('YNEOS'[len({sum(c) for i in range(n + 1) for c in combinations(a, i)}) >> n::2])

Solution (Python):
from itertools import *
for s in [*open(0)][2::2]:
    a = (*map(int, s.split()),)
    n = len(a)
    print('YNEOS'[len({*map(sum, chain(*(combinations(a, i) for i in range(n + 1))))}) >> n::2])

Solution (Python):
from itertools import combinations
T = int(input())
for i in range(T):
    n = int(input())
    arr = list(map(int, input().split()))
    if n == 1:
        if arr[0] != 0:
            print('NO')
        else:
            print('YES')
        continue
    h = dict()
    t = 0
    for j in range(1, n + 1):
        for k in combinations(arr, j):
            l = sum(k)
            if l == 0:
                t = 1
                print('YES')
                break
            elif l in h:
                t = 1
                print('YES')
                break
            else:
                h[l] = 1
        if t == 1:
            break
    if t != 1:
        print('NO')