Partition Equal Subset Sum

Given an array of positive integers, determine whether the array can be partitioned into two subsets such that the sums of the elements in both subsets are equal. Formally, let \(S\) be the sum of all elements in the array. If \(S\) is odd, the answer is False. Otherwise, check if there exists a subset where the sum of its elements is \(\frac{S}{2}\). This problem can be solved using a dynamic programming approach.

Example 1: For the input array [1, 5, 11, 5], the total sum is 22 and \(\frac{22}{2} = 11\). A valid partition is [11] and [1, 5, 5], both summing to 11, so the output is True.

Example 2: For the input array [1, 2, 3, 5], the total sum is 11 which is odd. Therefore, a valid partition is not possible and the output is False.

inputFormat

The input is read from stdin and consists of two lines. The first line contains a single integer \(n\) representing the number of elements. The second line contains \(n\) space-separated positive integers representing the elements of the array.

For example:

4
1 5 11 5

outputFormat

The output is a single line printed to stdout containing either True or False, indicating whether the array can be partitioned into two subsets with equal sum.

## sample

4
1 5 11 5

True

</p>