Partition Equal Subset Sum

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

More formally, given a list \(nums\) of length \(n\), decide whether there exists a subset \(S \subseteq \{0, 1, \ldots, n-1\}\) such that

[ \sum_{i \in S} nums[i] = \sum_{j \notin S} nums[j]. ]

If the total sum of the list is odd, the answer is obviously False. Otherwise, the problem reduces to finding a subset of numbers that sums to \(\frac{\text{total sum}}{2}\).

Input and Output

The input contains several test cases. The first line of the input is an integer \(T\), indicating the number of test cases. For each test case, the first line is an integer \(n\) representing the number of elements in the list, followed by a line with \(n\) space-separated integers. For each test case, print True if the list can be partitioned as required, otherwise print False.

Examples:

• Input: 4\n1 5 11 5 → Output: True
• Input: 4\n1 2 3 5 → Output: False

inputFormat

The first line contains an integer \(T\) indicating 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.
• The second line contains \(n\) space-separated integers.

outputFormat

For each test case, output a single line containing either True or False indicating whether the list can be partitioned into two subsets with equal sum.

## sample

2
2
1 1
1
2

True
False

</p>