Partition Equal Subset Sum

Given an array of positive integers, determine whether it is possible to partition the array into two subsets such that the sum of the elements in both subsets is equal.

You are given an array \( A = [a_1, a_2, \dots, a_n] \). Let \( S \) be the total sum of the array. The partition is possible if and only if:

[ S \equiv 0 \pmod{2} ]

and there exists a subset of \( A \) whose sum is \( \frac{S}{2} \). Use dynamic programming to solve this problem efficiently.

inputFormat

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

outputFormat

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

4
1 5 11 5

True