Equal Sum Partition Problem

You are given an array of positive 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. In other words, let (S) be the sum of all elements in the array. The task is to decide whether there is a subset of the array with sum (\frac{S}{2}) (which implies that (S) must be even).

The underlying idea is to use dynamic programming to solve this subset-sum problem. A valid partition exists if and only if there is a subset whose sum equals (\frac{S}{2}); otherwise, it does not. If such a partition is possible, print YES, otherwise print NO.

inputFormat

The input is read from 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 positive integers.

For example:

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

outputFormat

For each test case, output a single line to standard output (stdout) containing either YES if the array can be partitioned into two subsets with equal sum or NO otherwise.## sample

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

YES
NO
YES