Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example 1: Input: [1, 5, 11, 5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2: Input: [1, 2, 3, 5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.
Backpack problem: dp[i][j] means if the first i elements can sum up to value j
dp[i][j] = dp[i-1][j] || (j>=nums[i-1] && dp[i-1][j-nums[i-1]])
the result is if the half sum of the array can be summed up by elements in the array
public class Solution {
public boolean canPartition(int[] nums) {
if (nums.length == 0) return true;
int volume = 0;
for (int num : nums) {
volume += num;
}
if (volume % 2 == 1) return false;
volume /= 2;
boolean[] dp = new boolean[volume+1];
dp[0] = true;
for (int i=1; i<=nums.length; i++) {
for (int j=volume; j>=0; j--) {
dp[j] = dp[j] || (j>=nums[i-1] && dp[j-nums[i-1]]);
}
}
return dp[volume];
}
}