【一天一大 lee】分割等和子集 (难度:中等) - Day20201011
【一天一大 lee】分割等和子集 (难度:中等) - Day20201011
前端小书童
发布于 2020-10-14 17:20:34
发布于 2020-10-14 17:20:34
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]
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-10-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录