Equal Sum Partition

Given an integer array, determine if it can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Formally, given a set (S) of integers, check whether there exists a subset (S_1) satisfying (\sum_{x\in S_1} x = \frac{1}{2}\sum_{x\in S} x). Note that if (\sum_{x\in S} x) is odd, it is impossible to partition (S) into two subsets with equal sum.

inputFormat

Input consists of two lines. The first line contains an integer (n), representing the number of elements in the array. The second line contains (n) space-separated integers.

outputFormat

Output a single line containing either true if such a partition exists, or false if it does not.## sample

4
1 5 11 5

true