class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) { // add them all
sum += num;
}
if (sum % 2 == 1) { // if two sets are equal, sum must be even
return false;
}
int n = nums.length;
int m = sum/2; // become 01 backpack problems, target is sum/2
boolean dp[][] = new boolean[n+1][m+1];
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (j >= nums[i-1]) {
dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]];
} else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n][m]; // when sum/2 (two sets are equal), is it true?
}
}
1D space
T: O(mn)
S: O(n)
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
int m = nums.length;
int n = sum/2;
boolean[] dp = new boolean[n+1]; // 0 ~ m number, 0~n weight
dp[0] = true;
for (int i = 1; i <= m; i++) {
for (int j = n; j >= 0; j--) { // when go to 1D, should reverse to do, or will become complete kapnack
int curr = nums[i-1]; // i-1 !
if (j >= curr) {
// choose or not choose
dp[j] |= dp[j - curr];
}
}
}
return dp[n]; // we want sum/2
}
}ja
或者把 j >= nums[i-1] 寫在 for loop 就可以了, 少一個 if 條件
```java
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
int m = nums.length;
int n = sum/2;
boolean[] dp = new boolean[n+1];
dp[0] = true; // sum == 0, always true
for (int i = 0; i < m; i++) {
for (int j = n; j >= nums[i]; j--) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
return dp[n];
}
}
```
