Equal Sum Subset Partition

Given an array of integers, determine whether it is possible to partition it into two subsets such that the sum of the elements in each subset is equal. In other words, check if there exists a subset \(S\) of the array \(\text{nums}\) such that:

\[ \sum_{x \in S} x = \sum_{x \in \text{nums} \setminus S} x \]

If such a partition exists, output True; otherwise, output False.

inputFormat

The input begins with an integer T on a single line indicating the number of test cases. Each test case consists of two lines. The first line of each test case contains a single integer n, the number of elements in the array. The second line contains n space-separated integers representing the array.

outputFormat

For each test case, output a single line. Print True if the array can be partitioned into two subsets with equal sum, and False otherwise.

## sample

5
4
1 5 11 5
4
1 2 3 5
1
1
2
1 1
3
1 2 5

True
False
False
True
False

</p>