Equal Subset Sum Partition

Given an array of non-negative integers, determine whether it can be partitioned into two subsets with an equal sum. Formally, you are to decide if there exists a subset (S) of the array (A) such that [ \sum_{x\in S} x = \frac{\sum_{x\in A} x}{2} ] For example, for the array [1, 5, 11, 5], the partition [1, 5, 5] and [11] produces equal sums. Note that an empty array is considered to have an equal partition (with both subsets summing to 0).

inputFormat

The first line of input contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated non-negative integers. For an empty array, the first line will be 0.

outputFormat

Output a single line containing either "True" if the array can be partitioned into two subsets with equal sum, or "False" otherwise.## sample

4
1 5 11 5

True