Equal Subset Sum Partition

You are given an array of integers. Your task is to determine whether it is possible to partition the array into two subsets such that the sum of the elements in both subsets is equal. The partition is feasible only if the total sum of the array is even. In that case, you need to check if there exists a subset whose sum is equal to \(\frac{S}{2}\), where \(S\) is the total sum of the array.

Input Example: Suppose you have an array [1, 5, 11, 5]. The total sum is 22 and half of it is 11. Since there exists a subset [11] (or [1,5,5]) that sums to 11, the answer would be YES. However, if no such subset exists, print NO.

This problem is a classic variation of the subset sum problem and can be solved efficiently using dynamic programming.

inputFormat

The input is given via standard input (stdin). The first line contains an integer T representing the number of test cases. Each test case consists of two lines:

• The first line contains a single integer N representing the number of elements in the array.
• The second line contains N space-separated integers representing the array elements.

outputFormat

For each test case, print on a new line YES if the array can be partitioned into two subsets with equal sum; otherwise, print NO.

## sample

2
4
1 5 11 5
3
1 1 3

YES
NO

</p>