Given a non-empty array nums 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.
Example 1:
Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: nums = [1,2,3,5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.
Constraints:
1 <= nums.length <= 2001 <= nums[i] <= 100
Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
* Intuition: This is a variation of knapsack dp. We precompete the target sum and find the knapsack.
* Time Complexity: O(N ^ 2) .
* Space Complexity: O(N ^ 2).
*/
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int i : nums) {
sum += i;
}
if (sum % 2 == 1) {
return false;
}
return knapsackBoolean(nums, sum / 2);
}
boolean knapsackBoolean(int[] w, int c) {
boolean[][] dp = new boolean[w.length + 1][c + 1];
for (int i = 0; i <= w.length; i++) {
for (int j = 0; j <= c; j++) {
if (i == 0) {
dp[i][j] = false;
}
if (j == 0) {
dp[i][j] = true;
}
if (i > 0 && j > 0) {
if (w[i - 1] <= j) {
dp[i][j] = dp[i - 1][j - w[i - 1]] || dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
}
return dp[w.length][c];
}
boolean knapsack(int[] w, int c) {
int[][] dp = new int[w.length + 1][c + 1];
for (int i = 1; i <= w.length; i++) {
for (int j = 1; j <= c; j++) {
if (w[i - 1] <= j) {
dp[i][j] = Math.max(w[i - 1] + dp[i - 1][j - w[i - 1]], dp[i - 1][j]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[w.length][c] == c;
}
}
