Cocolib

Appearance

On this page

分割等和子集 ​

TIP

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

思路 ​

动规五部曲 ​

  1. 确定dp数组以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

将问题转化为0-1背包问题，如果说当前数组看作物品，只要物品能够装满背包容量为sum/2就返回true，否则返回false

js
var canPartition = function(nums) {
    let n = nums.reduce((pre,cur)=>pre+cur,0)/2 //背包容量
    let dp =[]
    for(let j=0;j<=n;j++){
        dp[j] = 0
    }
    for(let i=0;i<nums.length;i++){     //物品
        for(let j=n;j>=nums[i];j--){           //背包
            dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i])
        }
    }
    if(dp[n]===n)   return true
    else return false 
};