二刷 07/2022
Version #1 0/1 Knapsack
Time O(N * Sum)
Space O(N * Sum)
Runtime: 26 ms, faster than 91.77% of Java online submissions for Partition Equal Subset Sum.
Memory Usage: 43.5 MB, less than 75.86% of Java online submissions for Partition Equal Subset Sum.
class Solution {
public boolean canPartition(int[] nums) {
int target = 0;
for (int num : nums) {
target += num;
}
if (target % 2 != 0) {
return false;
}
target /= 2;
// dp[i][s] - [0, i) numbers can add up to s
boolean[][] dp = new boolean[nums.length + 1][target + 1];
dp[0][0] = true;
for (int i = 1; i <= nums.length; i++) {
for (int j = target; j >= 0; j--) {
if (dp[i - 1][j] || (j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]])) {
dp[i][j] = true;
}
}
if (dp[i][target]) {
return true;
}
}
return dp[nums.length][target];
}
}
Version #2 HashSet
Time O(N * Sum of all numbers)
Space O(Sum of all numbers)
Runtime: 410 ms, faster than 5.82% of Java online submissions for Partition Equal Subset Sum.
Memory Usage: 117.8 MB, less than 6.46% of Java online submissions for Partition Equal Subset Sum.
class Solution {
public boolean canPartition(int[] nums) {
int target = 0;
for (int num : nums) {
target += num;
}
if (target % 2 != 0) {
return false;
}
target /= 2;
Set<Integer> visited = new HashSet<>();
visited.add(0);
for (int num : nums) {
Set<Integer> newSum = new HashSet<>();
for (int prev : visited) {
if (prev + num == target) {
return true;
}
newSum.add(prev + num);
}
visited.addAll(newSum);
}
return false;
}
}
一刷 06/2022
Version #1 0/1 Knapsack DP
It could be optimized to 1d DP
Time O(N*Sum)
Space O(N*Sum)
Runtime: 51 ms, faster than 61.41% of Java online submissions for Partition Equal Subset Sum.
Memory Usage: 54.3 MB, less than 44.88% of Java online submissions for Partition Equal Subset Sum.
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
sum /= 2;
// System.out.printf("sum=%d\n", sum);
// The [0, i) numbers can sum up to j
boolean[][] dp = new boolean[nums.length + 1][sum + 1];
// The first 0 number can sum up to 0
dp[0][0] = true;
for (int i = 1; i <= nums.length; i++) {
// the nums[i - 1] item
int num = nums[i - 1];
for (int j = 0; j < sum + 1; j++) {
if (num <= j) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
} else {
dp[i][j] = dp[i - 1][j];
}
}
if (dp[i][sum]) {
return true;
}
}
return dp[nums.length][sum];
}
}
No comments:
Post a Comment