Equal Sum Partition

You are given an array of integers. Your task is to determine if the array can be partitioned into two subsets such that the sum of the elements in both subsets is equal.

More formally, let \(S\) be the total sum of the array. You need to determine if there exists a subset whose sum is equal to \(\frac{S}{2}\). If \(S\) is odd, then it is impossible to partition the array into two subsets of equal sum.

This problem can be efficiently solved using dynamic programming with a time complexity of \(O(n \cdot \frac{S}{2})\), where \(n\) is the number of elements in the array.

inputFormat

The first line of input contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers representing the array elements. ((1 \leq n \leq 50), each element is a positive integer up to 100)

outputFormat

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

4
1 5 11 5

True