一、题目内容 中等
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例1:
输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11]
示例2:
输入:nums = [1,2,3,5] 输出:false 解释:数组不能分割成两个元素和相等的子集。
提示:
1 <= nums.length <= 200
-
二、解题思路
只有确定了如下四点,才能把01背包问题套到本题上来。
背包的体积为 sum / 2
- 背包要放入的商品(集合里的元素)重量为 元素的数值,价值也为元素的数值
- 背包如果正好装满,说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入。
以上分析完,我们就可以套用01背包,来解决这个问题了。
动规五部曲分析如下:
- 确定dp数组以及下标的含义
01背包中,dp[j] 表示: 容量为 j 的背包,所背的物品价值可以最大为 dp[j]。
套到本题,dp[j] 表示 背包总容量是 j,最大可以凑成 j 的子集总和为 dp[j]。
- 确定递推公式
01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
本题,相当于背包里放入数值,那么物品 i 的重量是 nums[i],其价值也是 nums[i]。
所以递推公式:dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
- dp 数组如何初始化
在 01 背包,一维 dp 如何初始化,已经讲过,从 dp[j] 的定义来看,首先 dp[0] 一定是 0。
如果题目给的价值都是正整数,那么非 0 下标都初始化为 0 就可以了。
如果题目给的价值有负数,那么非 0 下标就要初始化为负无穷。
这样才能让 dp 数组在递归公式的过程中取的最大的价值,而不是被初始值覆盖了。
- 确定遍历顺序
如果使用一维 dp 数组,物品遍历的 for 循环放在外层,遍历背包的 for 循环放在内层,且内层 for 循环倒序遍历!
for (let i = 0; i < nums.length; i++) {
for (let j = mid; j >= nums[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])
}
}
- 举例推导 dp 数组
dp[i] 的数值一定是小于等于 i 的。
如果 dp[i] === i 说明,集合中的子集总和正好可以凑成总和 i,理解这一点很重要。
用例1,输入[1,5,11,5] 为例,如图
三、具体代码
/**
* @param {number[]} nums
* @return {boolean}
*/
var canPartition = function (nums) {
const sum = nums.reduce((pre, cur) => pre + cur, 0)
const mid = sum / 2
if (sum % 2) return false
const dp = new Array(mid + 1).fill(0)
nums.sort((a, b) => a - b)
for (let i = 0; i < nums.length; i++) {
for (let j = mid; j >= nums[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])
}
}
if (dp[mid] === mid) return true
return false
};