416. 分割等和子集——medium-dp

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

注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum

思路：
典型01背包问题，令 dp[i][j] 表示从前 i 个元素中挑选一些正整数，使其和为 j 的真假，对于nums[i]
dp[i][j] =dp[i-1] || dp[i][j-nums[i]]
可以看出每一行的状态只与上一行有关，可以用滚动数组优化空间复杂度：
dp[j] |= dp[j-nums[i]]
复杂度分析
时间复杂度O(n*target) target 为数组元素和的一半
空间复杂度O(target)

var canPartition = function(nums) {
    if(nums.length<2) return false;
    let max=0
    let sum = nums.reduce((prev,val)=>{
        max =Math.max(max,val)
        return prev+val
    },0)
    if(sum % 2 !== 0) return false;
    let target = sum/2;
    if(target<max) return false;
    let dp = new Array(target+1).fill(false)
    dp[0]=true;
    for(let i = 0; i < nums.length; i++){
        for(let j = target;j>=nums[i];j--){
            dp[j] |= dp[j-nums[i]]; 
        }
    }
    return dp[target]
};