Partition Equal Subset Sum

Given an array of integers, determine whether it can be partitioned into two subsets such that the sum of the elements in each subset is equal. Formally, given an array \(A\) of size \(n\), check if there exists a subset of \(A\) that sums to \(\frac{\text{sum}(A)}{2}\).

This problem can be efficiently solved using dynamic programming. If the total sum of the array is odd, then it is impossible to split it into two equal parts. Otherwise, use a 1-dimensional DP array where \(dp[j]\) indicates if a subset with sum \(j\) can be reached. The transition is defined by:

[ \text{dp}[j] = \text{dp}[j] ;\textbf{or}; \text{dp}[j - \text{num}], \quad \text{for each } j \text{ from } \frac{\text{sum}(A)}{2} \text{ down to } \text{num}, ]

Output True if such a partition exists, and False otherwise.

inputFormat

The input is read from stdin and consists of two lines:

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

outputFormat

Output to stdout a single line containing either True if the array can be partitioned into two subsets with equal sum, or False otherwise.

4
1 5 11 5

True