Implement the canPartitionEqualSum method that checks whether the array can be split into two subsets with equal sum.
The input contains an integer array nums and its length size. Your task is to check whether the array can be divided into two subsets with equal sum.
If the total sum is odd, equal partition is impossible. If the total sum is even, the problem becomes checking whether any subset can make half of the total sum. For example, [1,5,11,5] can be split into [11] and [1,5,5], so the answer is true.
Example 1
[1,5,11,5]4trueExample 2
[1,2,3,5]4falseExample 3
[2,2,3,5]4falseFirst calculate the total sum of the array. If it is odd, return false immediately.
Otherwise, set target = total / 2. Now check whether there is a subset whose sum is equal to this target.
Use a boolean dynamic programming array. dp[x] tells whether sum x can be formed using the numbers processed so far. Loop backward for each number so that each array value is used only once.
Pseudocode:
function canPartitionEqualSum(nums, size):
total = sum of all values in nums
if total % 2 != 0:
return false
target = total / 2
dp = boolean array of target + 1 values filled with false
dp[0] = true
for each num in nums:
for sumValue from target down to num:
dp[sumValue] = dp[sumValue] or dp[sumValue - num]
return dp[target]