3
416.Pacific_Atlantic_Water_Flow
source link: http://muyunyun.cn/blog/qq9zzeze/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
416. Partition Equal Subset Sum
Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Example 1:
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
Constraints:
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 100
Analyze
- 若数组中所有元素相加之和为奇数，则不满足。
- 判断数组中部分元素相加之和是否达到 sum / 2。
两个子数组中的值之和相等条件为：对于任何一子数组，sum / 2 刚好分配完。
- 使用 nums[i]，剩余背包为 target = target - nums[i]，在 [i + 1, nums.length - 1] 区间内找寻。
- 没有使用 nums[i]，剩余背包为 target，在 [i + 1, nums.length - 1] 区间内找寻。
* @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 !== 0) return false
const result = recursive(nums, 0, sum / 2, {})
return result
var recursive = function(nums, index, target, cache) {
if (target < 0 || index === nums.length) return false
if (target === 0) return true
if (typeof cache[`${index}-${target}`] === 'boolean') {
return cache[`${index}-${target}`]
return cache[`${index}-${target}`] = (recursive(nums, index + 1, target - nums[index], cache)
|| recursive(nums, index + 1, target, cache))
在上文递归题解中，核心思路是通过 target = target || (target - nums[i]) 来对数组中的剩余部分来递归计算。
我们也可以使用动态规划。
以 nums = [1,5,11,5] 为例进行分析：
dp[i][j] 的语义：在 nums 数组 0 到 i 的范围内，挑选若干个值，使它们之和为 j。
- 初始状态：dp[0][j]
- 状态转移：dp[i][j] = dp[i - 1][j] || dp[i - 1]j - nums[i]]
dp[i][0] 声明为 true，可以理解为视场景决定的兜底，比如 dp[1][5] = dp[0][5] || dp[0][0] = false || dp[0][0]，推理得 dp[0][0] 应为 true。
* @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 !== 0) return false
const arr = [[true]]
for (let j = 1; j <= sum / 2; j++) {
arr[0][j] = j === nums[0]
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j <= sum / 2; j++) {
if (!arr[i]) {
arr[i] = []
arr[i][j] = arr[i - 1][j] || arr[i - 1][j - nums[i]] || false
return arr[nums.length - 1][sum / 2]
当前开辟了背包容量 * 物品容量个空间，根据状态转移公式 dp[i][j] = dp[i - 1][j] || dp[i - 1]j - nums[i]] 可以发现，空间其实只用开辟背包容量 * 2行就可以满足该需求，甚至只需要背包容量 * 1行也可以满足，从而将二维数组转化为一维数组。接着来进一步优化：
var canPartition = function(nums) {
let sum = 0
for (let i = 0; i < nums.length; i++) {
sum += nums[i]
if (sum % 2 !== 0) return false
const arr = [true]
for (let j = 1; j <= sum / 2; j++) {
arr[j] = j === nums[0]
for (let i = 1; i < nums.length; i++) {
for (let j = sum / 2; j >= 0; j--) {
arr[j] = arr[j] || arr[j - nums[i]] || false
return arr[sum / 2]
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK