Equal Subset Sum Partition

You are given a list of integers. Your task is to determine whether it is possible to partition the list into two subsets such that the sum of the elements in both subsets is equal.

Formally, given an array nums of n integers, determine if there exists a subset whose sum is \(\frac{S}{2}\), where \(S\) is the total sum of all elements in the array. If such a subset exists, output "YES", otherwise output "NO".

Note: The problem can be solved using dynamic programming. If the total sum is odd, then the answer is "NO" immediately.

inputFormat

The first line of input contains a single integer T (\(1 \leq T \leq 100\)), representing the number of test cases.

For each test case:

• The first line contains an integer n (\(1 \leq n \leq 1000\)), the number of elements in the list.
• The second line contains n space-separated integers, each representing an element of the list.

It is guaranteed that the sum of all elements in each test case will not exceed \(10^5\).

outputFormat

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

## sample

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

YES
NO
NO
YES

</p>