Partition Equal Subset Sum

You are given a positive integer n and an array of n integers. The task is to determine whether it is possible to partition the array into two subsets such that the sum of the elements in both subsets is equal.

This is equivalent to checking if there exists a subset of the array whose sum is equal to \(\frac{S}{2}\), where \(S\) is the total sum of the array. Note, if \(S\) is odd then it is impossible to split it into two equal subsets.

You are required to read from standard input (stdin) and write your result to standard output (stdout). The output should be True if such a partition exists, and False otherwise.

inputFormat

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

outputFormat

Output a single line containing either True or False indicating whether the array can be partitioned into two subsets with equal sum.

4
1 5 11 5

True