Equal Sum Partition

You are given a list of integers representing the number of employees in different departments. Your task is to determine whether it is possible to partition the departments into two groups such that the sum of the numbers of employees in each group is equal.

Formally, given a list groups of non-negative integers, determine if there exists a subset whose sum is exactly \(\frac{\text{total\_sum}}{2}\), where \(\text{total\_sum}\) is the sum of all elements in groups. Note that if \(\text{total\_sum}\) is odd, then such a partition is impossible.

Input Format: The input contains multiple test cases. The first line of input is an integer T, representing the number of test cases. For each test case, the first line contains an integer n denoting the number of departments, followed by a line with n space-separated integers, where each integer represents the number of employees in that department.

Output Format: For each test case, output a single line containing either "YES" if such a partition is possible, or "NO" if it is not.

For example, consider the test case:

1
4
1 5 11 5

The output should be:

YES

Remember to use efficient algorithms since the number of departments can be large.

inputFormat

The first line contains an integer T — the number of test cases. Each test case begins with an integer n — the number of departments, followed by a line with n space-separated integers representing the number of employees in each department.

outputFormat

For each test case, output on a new line "YES" if the list can be partitioned into two subsets with equal sum, or "NO" otherwise.

## sample

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

YES
NO
NO

</p>