Equal Sum Partition Challenge

Given an array of positive integers, determine if it is possible to partition the array into two subsets such that the sums of the two subsets are equal.

Let \(S\) be the total sum of the elements in the array. The task is to decide whether there exists a subset whose sum is \(\frac{S}{2}\) (this is only possible if \(S\) is even). If such a partition exists, print YES; otherwise, print NO.

The solution must read input from stdin and write the results to stdout. It is required that your solution can handle large arrays efficiently.

inputFormat

Input (stdin):

• The first line contains a single integer \(T\) representing the number of test cases.
• For each test case, the first line contains an integer \(n\) representing the number of elements in the array.
• The next line contains \(n\) space-separated positive integers.

outputFormat

Output (stdout):

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

## sample

3
4
5 2 3 6
6
10 5 5 5 2 3
8
2 2 2 2 2 2 2 2

YES
YES
YES

</p>