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.
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int x : nums)
sum += x;
if (sum % 2 != 0)
return false;
int n = nums.length;
// using subset sum problem to find a subset which has sum = total sum/2
boolean dp[][] = new boolean[n + 1][sum / 2 + 1];
// base case when sum->0 then answer is always true
for (int i = 0; i <= n; i++)
dp[i][0] = true;
// dp[i][k] -> tells us if it is possible to form a subsequence from (0,i) with
// sum=k
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= sum / 2; k++) {
if (k - nums[i - 1] >= 0)
dp[i][k] = dp[i - 1][k] || dp[i - 1][k - nums[i - 1]];
else
dp[i][k] = dp[i - 1][k];
}
}
return dp[n][sum / 2];
}
}