Equal Sum Partition with Negative Numbers

You are given an array of integers, which may include negative numbers. Your task is to determine whether it is possible to partition the array into two subsets such that the sum of elements in both subsets are equal.

Let \( S \) be the sum of all elements in the array. A necessary condition for a valid partition is that \( S \) is even. In that case, the problem reduces to finding a subset \( S_1 \) such that \[ \sum_{x \in S_1} x = \frac{S}{2} \] If such a subset exists, the remainder of the elements form the second subset with the same sum.

You are required to use a dynamic programming approach to solve this problem and your solution must correctly handle negative numbers.

inputFormat

The input is read from standard input (stdin) and has the following format:

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

outputFormat

The output is written to standard output (stdout) and should be a single line containing either True or False (without quotes), indicating whether a valid partition exists.

4
1 5 11 5

True