Equal Halves Partition

Given an even-length array of integers, determine whether the array can be rearranged into two halves such that the sum of the elements in each half is equal.

Formally, let \( n \) be an even integer and \( A = [a_1, a_2, \dots, a_n] \) be an array of integers. You need to determine if there exists a subset \( S \subset A \) with exactly \( \frac{n}{2} \) elements such that

[ \sum_{x \in S} x = \frac{1}{2}\sum_{x \in A} x. ]

If such a partition exists, print YES; otherwise, print NO.

inputFormat

The input is read from standard input and consists of multiple test cases.

The first line contains an integer \( T \) \( (1 \le T \le 100) \), the number of test cases. Each test case is presented in the following format:

• The first line contains an integer \( n \) \( (1 \le n \le 30) \) representing the number of elements in the array. Note that \( n \) must be even for a valid partition.
• The second line contains \( n \) space-separated integers \( a_1, a_2, \dots, a_n \) \( (-10^5 \le a_i \le 10^5) \) representing the elements of the array.

outputFormat

For each test case, output a single line containing YES if the array can be rearranged into two halves with equal sums, or NO otherwise.

## sample

3
4
1 1 2 2
5
1 2 3 4 5
6
3 3 3 3 6 6

YES
NO
YES

</p>