20201011
题目:
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例:
- 示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
- 示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
抛砖引玉
思路
先得到数组所有元素的和:
- 如果和为奇数则一定不能满足要求
- 如果和为偶数:
- 其是否有子集的和等于所有和的一半
抛砖引玉
递归回溯
/**
* @param {number[]} nums
* @return {boolean}
*/
var canPartition = function(nums) {
// 求和
let sum = 0
for (let i = 0; i < nums.length; i++) {
sum += nums[i]
}
// 如果和为奇数则一定不能满足要求
if (sum % 2) return false
// 递归回溯枚举子集
let halfSum = parseInt(sum / 2, 10),
map = new Map()
function helper(index, childSum) {
// 记录已经枚举的组合,避免重复计算
const flag = index + '-' + childSum
if (map.has(flag)) return map.get(flag)
if (index >= nums.length || childSum > halfSum) return false
if (childSum === halfSum) return true
const child =
helper(index + 1, childSum) || helper(index + 1, childSum + nums[index])
map.set(flag, child)
return child
}
return helper(0, 0)
}
动态规划
- 状态定义:dp[i][j]表示在数组 nums 从 0 到 i 区间是否存在子集和为 j,有则为 true,无则为 false
- 对应 nums[i],在自区间中存在选择和不选择两种情况:
- 选择:,注意:j – nums[i]>=0,即 nums[i]<= j
- 不选择:
dp[i][j]边界
- i 是 nums 的索引则:i <= nums.length
- j 是 nums 子集和,且本题求的子集和为 nums 和的一半则:j <= halfSum,注意 j 是从 0 开始填充则在生成 dp 数组时数组的长度应该为 halfSum+1
dp[i][j]初始化
- 数组长度小于 2 或者和为奇数均不存在满足条件的情况
- dp[i][0],即 0 到 i 和为 0 的情况一定存在(均不选择)true
- ,即 选择第一个元素和满足条件
var canPartition = function(nums) {
// 求和
let sum = 0,
len = nums.length
for (let i = 0; i < len; i++) {
sum += nums[i]
}
// 如果和为奇数则一定不能满足要求
if (sum % 2 || len < 2) return false
let halfSum = parseInt(sum / 2, 10),
dp = Array(len)
.fill(0)
.map(() => Array(halfSum + 1, false))
// 初始化
for (let i = 0; i < len; i++) {
dp[i][0] = true
}
dp[0][nums[0]] = true
// 遍历nums对nums[i]枚举选择和不选择两种情况
for (let i = 1; i < len; i++) {
const num = nums[i]
for (let j = 1; j <= halfSum; j++) {
if (j >= num) {
// 对已知可能的情况取或
// dp[i][j] = Boolean(dp[i - 1][j] || dp[i - 1][j - num])
dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num]
} else {
dp[i][j] = dp[i - 1][j]
}
}
}
return dp[len - 1][halfSum]
}
降维
var canPartition = function(nums) {
// 求和
let sum = 0,
len = nums.length
for (let i = 0; i < len; i++) {
sum += nums[i]
}
// 如果和为奇数则一定不能满足要求
if (sum % 2) return false
let halfSum = parseInt(sum / 2, 10),
dp = Array(halfSum + 1).fill(false)
dp[0] = true
for (let i = 0; i < len; i++) {
const num = nums[i]
// 因为j-num一定是小于j的,j-num是dp[j]的前置条件,则需要倒序保证求dp[j]时dp[j-num]已确定
// 如果采用正序,dp[j]中j在递增的过程中会反复修改dp[j-num]的值
for (let j = halfSum; j >= num; --j) {
dp[j] = dp[j] | dp[j - num]
}
}
return dp[halfSum]
}
正文完