题目
给你一个?只包含正整数?的?非空?数组?
nums?。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
思路
- 思路
转换为 「0 - 1」 背包问题：是否可以从输入数组中挑选出一些正整数，使得这些数的和?等于?整个数组元素的和的一半
它的特点是：「每个数只能用一次」。解决的基本思路是：物品一个一个选，容量也一点一点增加去考虑，这一点是「动态规划」的思想，特别重要。
- 状态与状态转移方程
dp[i][j]表示从[0-i]的区间中挑选正数(每个数只能用一次)使之等于j
dp[i][j]=dp[i-1][j](不选nums[I])? ?||? dp[i-1][j-nums[i]](选nums[I])
?答案
/**
* @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===1) return false;
sum = sum / 2
var dp = new Array(nums.length + 1).fill(0).map(v => (new Array(sum + 1).fill(false)))
dp[0][0] = true;
for(let j=1;j<=sum;j++){
for(let i=1;i<=nums.length;i++){
dp[i][j]=dp[i-1][j]
if(nums[i-1]===j) dp[i][j]=true;
//因为nums[i-1]>j的话 其实不需要考虑选nums[I]的时候：dp[i-1][j-nums[i-1]]
if(nums[i-1]<j) dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
}
}
return dp[nums.length][sum];
};