Partition Equal Subset Sum

Given a list of integers, determine whether it is possible to partition the list into two subarrays with equal sum. Let the total sum be \( S = \sum_{i=1}^{n} \text{nums}_i \). A necessary condition for such a partition is that \( S \) is even. If \( S \) is even, then check if there exists a subset of the list that sums to \( S/2 \).

For example, for the list [1, 5, 11, 5], the total sum is 22 which is even, and there exists a partition [1, 5, 5] and [11] where both subsets sum to 11. Your task is to determine whether such a partition exists.

inputFormat

The first line of input contains an integer ( n ), the number of elements. The second line contains ( n ) space-separated integers representing the list.

outputFormat

Output a single line containing either "True" or "False" (without quotes) indicating whether the list can be partitioned into two subarrays with equal sum.## sample

4
1 5 11 5

True