Partition Array into Two Equal Target Sum Subsets

You are given an array of integers and a target integer. Your task is to determine whether it is possible to partition the array into two disjoint subsets such that each subset sums to target. Note that for this to be possible, the sum of all elements in the array must be exactly 2 \(\times\) target.

If the total sum is not equal to \(2 \times target\), then the answer is immediately False because it is impossible to form two subsets with sum equal to target each.

This problem can be efficiently solved using dynamic programming. One approach is to use a 1D DP array where dp[i] indicates whether a subset sum of i is achievable with the current numbers. Start by initializing dp[0] as True and then update the DP array for each number in the array.

Input/Output: The input is read from stdin and the output is written to stdout.

inputFormat

The first line contains a single integer n denoting the number of elements in the array. The second line contains n space-separated integers which represent the elements of the array. The third line contains the target integer.

outputFormat

Output True if the array can be partitioned into two subsets where each subset sums to the target integer; otherwise, output False.

4
1 5 11 5
11

True