LeetCode 416 - Partition Equal Subset Sum

作者 QIFAN 日期 2017-01-04
LeetCode 416 - Partition Equal Subset Sum

原题链接:416. Partition Equal Subset Sum


题干

给定一个非空非负集合,判断是否可以分成两个总和相等的子集。

注:

  • 数组中每个元素都不会超过 100
  • 数组大小不超过 200

思路

集合的总和不会超过 100 * 200 = 20000 。

我第一想法是,先排序,然后算出总和 sum ,然后分别看一个数的总和,两个数的总和 … 是否等于 sum / 2 。 这样子最坏情况,总之很大。

naive 方法应该是找出所有子集,然后算,这样时间复杂度是 O(2^n) 。

然后我又去翻讨论了。发现了如下算法(见代码)。

这个方法的关键句就在于 dp[j] = dp[j] || dp[j - nums[i-1]]; 。dp[j] 代表能否组合成和为 j 的结果。对于每一个数字,选择都是两个,放或者不放。所以,如果不放第 i 个数字,那问题就变成了前 i - 1 个数字能否组合成和为 j 的结果;如果放第 i 个数字,那问题就变成了前 i - 1 个数字能否组合成和为 j - nums[i] 的结果。只要这两种情况有一种存在, dp[j] 就成立。另注:本题里因为多加了 dp[0] 所以 dp[i] 其实对应的是 nums[i - 1] 。

这个理解要非常感谢这篇文章的引导:背包问题

动态规划问题还是很难弄。

代码(cr):

public boolean canPartition(int[] nums) {
// 特殊情况
if (nums == null || nums.length == 0) {
return true;
}
// 求出总和先
int volumn = 0;
for (int num : nums) {
volumn += num;
}
// 若为奇数,返回 false
if (volumn % 2 != 0) {
return false;
}
volumn /= 2;
// dp def
boolean[] dp = new boolean[volumn + 1];
// dp init
dp[0] = true;
// dp transition
for (int i = 1; i <= nums.length; i++) {
for (int j = volumn; j >= nums[i-1]; j--) {
dp[j] = dp[j] || dp[j - nums[i-1]];
}
}
return dp[volumn];
}