Equal Subset Sum Partition

Given an array of integers, determine whether it is possible to partition it into two subsets such that the sum of the elements in both subsets is equal. Let the total sum of the array be \(S = \sum_{i=1}^n a_i\). If \(S\) is odd, partitioning is impossible. Otherwise, you need to determine if there exists a subset with sum \(\frac{S}{2}\).

The input is taken from standard input and the result should be printed to standard output.

inputFormat

The first line contains a single integer \(n\), the number of elements in the array. The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Print a single line containing either True or False (without quotes), indicating whether the array can be partitioned into two subsets of equal sum.

4
1 5 11 5

True