// dp[j] = dp[j] || dp[j - nums[i]] (nums[i] <= j <= target)
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num: nums) {
sum += num;
}
if (sum % 2 == 1) {
return false;
}
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
// 这个解法不对，对于 [1, 2, 5] 会返回 true，实际上应为 false
// 原因是 dp index 从 num to target，会涉及到元素的重复使用。num: 2, 会将 dp[4] 赋值为 true，原因是 dp[4] |= dp[4 - 2]，这里的 2 使用了两次。而从 target 到 num 的方向，就不会对该下 num 重复使用。
// for (int num: nums) {
// for (int i = num; i <= target; i++) {
// dp[i] |= dp[i - num];
// }
// }
for (int num: nums) {
for (int i = target; i >= num; i--) {
dp[i] |= dp[i - num];
}
}
return dp[target];
}
}
Backpack - 416. Partition Equal Subset Sum
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Given a non-empty array containing only positive integers...
- 这道题是一道变形题，可以变型到背包。 建立背包，表示是否可以拿到总和的一半。 注意，这道题不能变形到Presum，...
- Medium 这题原来的解法不是很好懂，有位拿到google offer的前辈说解法最重要的是“自己觉得好懂 + ...
- 原题地址 https://leetcode.com/problems/partition-equal-subset...
- apt-get 彻底卸载软件包 对于apt-get install安装的软件包，卸载方法如下： 删除PPA源 对于...
