416. Partition Equal Subset Sum (Medium)
https://leetcode.com/problems/partition-equal-subset-sum/
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.
Solutions
class Solution {
// This problem can be translated as find x numbers of which the total summation is sum/2,
// where x is a variable and not determined; sum is the total summation of elements in nums.
public boolean canPartition(int[] nums) {
if (nums == null || nums.length <= 1) {
return false;
}
int len = nums.length;
int sum = 0;
for (int i = 0; i < len; i++) {
sum += nums[i];
}
if (sum % 2 == 1) {
return false;
}
int target = sum / 2;
boolean[][] dp = new boolean[target + 1][len + 1];
// target 0, it is easy to get
Arrays.fill(dp[0], true);
// for the first column all set false, literally, elements in nums starts from 1 in dp
for (int i = 0; i < target + 1; i++) {
dp[i][0] = false;
}
dp[0][0] = true;
// i is the target to achieve
for (int i = 1; i < target + 1; i++) {
// we add (j-1)th num to gain i
for (int j = 1; j < len + 1; j++) {
// can I use result of dp[i][j-1] or incorporate nums[j-1] to come up with a new combination.
// 1. dp[i][j-1] is true which means elements in nums[0:j-2] can make sum to i, and we don't
// have to use nums[j-1]
if (dp[i][j - 1]) {
dp[i][j] = true;
continue;
}
// 2. dp[i - nums[j - 1]][j - 1] is true which means we can use nums[i-j], plus valid combination
// of target i-nums[j-1] of which elements are selected from nums[0:j-2] to achieve target i.
dp[i][j] = i >= nums[j - 1] && dp[i - nums[j - 1]][j - 1];
}
}
return dp[target][len];
}
}
Incorrect Solutions
class Solution {
// Incorrection idea.
// This problem can be translated as find x numbers of which the total summation is sum/2,
// where x is a variable and not determined; sum is the total summation of elements in nums.
public boolean canPartition(int[] nums) {
if (nums == null || nums.length <= 1) {
return false;
}
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
if (sum % 2 == 1) {
return false;
}
int target = sum / 2;
for (int i = 0; i <= target; i++) {
}
boolean ans = false;
return ans;
}
}