Array Differentiation
Contest: Codeforces Global Round 15
Difficulty rating: 1800
Tags: bitmasks, brute force, constructive algorithms, dfs and similar, dp, graphs, math

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

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

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.

Example input:
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

Example output:
YES
YES
NO
YES
YES

Editorial:
Suppose that a solution $$$b_1, \, \dots, \, b_n$$$ exists. For each $$$1 \le i \le n$$$, let $$$j_i, \, k_i$$$ be the indices such that $$$a_i = b_{j_i} - b_{k_i}$$$.
Consider the directed graph on vertices $$$1, \, \dots, \, n$$$, with the $$$n$$$ edges $$$j_i \rightarrow k_i$$$. If we ignore, for a moment, the orientations, we are left with an undirected graph with $$$n$$$ vertices and $$$n$$$ edges, which must contain a cycle (possibly a loop). Let $$$m$$$ be the length of one such cycle, and let $$$v_1, \, \dots, v_m$$$ be its vertices.
Now, of course $$$(b_{v_1} - b_{v_2}) + (b_{v_2} - b_{v_3}) + \cdots + (b_{v_m} - b_{v_1}) = 0$$$, since all the terms cancel out. Notice that, for each $$$i$$$, there exists $$$1 \le t_i \le n$$$ such that (indices are taken modulo $$$m$$$, so that $$$v_{m + 1} = v_1$$$) $$$$$$ b_{v_i} - b_{v_{i + 1}} = \begin{cases} a_{t_i} & \text{if there is an edge } v_i \rightarrow v_{i + 1}, \\ -a_{t_i} & \text{if there is an edge } v_i \leftarrow v_{i + 1}. \end{cases} $$$$$$
Thus, there must be a nonempty subset $$$\{t_1, \, \dots, \, t_m\} \subseteq \{1, \, \dots, \, n\}$$$ and a choice of signs $$$s_1, \, \dots, \, s_m$$$ ($$$s_i \in \{+1, \, -1\}$$$) such that $$$$$$\tag{$\star$} s_1a_{t_1} + \cdots + s_ma_{t_m} = 0. $$$$$$
Let us show that this condition is also sufficient for the existence of a valid sequence $$$b_1, \, \dots, \, b_n$$$. Suppose there exist $$$m$$$, $$$t_1, \, \dots, \, t_m$$$ and $$$s_1, \, \dots, \, s_m$$$ so that $$$(\star)$$$ holds. We construct $$$b_1, \, \dots, \, b_n$$$ as follows. Set $$$b_{t_1} = 0$$$. Then, inductively, for each $$$1 \le i < m$$$ set $$$b_{t_{i + 1}} = b_{t_i} - s_ia_{t_i}$$$. Finally, for $$$i \not\in \{t_1, \, \dots, \, t_m\}$$$, set $$$b_i = a_i$$$. It is easy to check that this construction works.
The algorithm that iterates over all $$$3^n - 1$$$ choices of the subset and the signs (for each $$$i$$$ we decide whether $$$a_i$$$ is included in the subset and if it is included, whether its sign is positive or negative) and checks if for one of them $$$(\star)$$$ holds, is sufficient to solve the problem under the given constraints.
Alternatively, one may treat the problem as a knapsack instance (the weights are $$$a_i$$$, but can be chosen with arbitrary sign, and we shall understand whether we can fill precisely a knapsack with $$$0$$$ capacity). With this approach, the complexity is $$$O(n^2\max|a_i|)$$$.
Bonus: Solve the problem with complexity $$$O(n3^{\frac{n}{2}})$$$.
Complexity: $$$O(n3^n)$$$.