416.分割等和子集

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

1. 每个数组中的元素不会超过 100
2. 数组的大小不会超过 200

示例 1:

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

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
  if (nums.length < 2) {
    return false;
  }
  const sum = nums.reduce((pre, next) => {
    return pre + next;
  }, 0)
  if (sum % 2 !== 0) {
    return false;
  }
  // 问题转化为 数组中能否找到一个集合,他的合等于sum/2 即01背包问题
  const target = sum / 2;
  // dp[i][j] 表示背包里前i个物品，能否找到一些物品凑出重量为j
  const dp = new Array(nums.length).fill(0).map(item => new Array(target).fill(false));
  for (let i = 0; i < nums.length; i++) {
    const a = nums[i];
    for (let j = 0; j <=target; j++) {
      if (j === 0) {
        dp[i][j] = true;
        continue;
      }
      // 只有一个物品
      if (i === 0) {
        dp[i][j] === j === nums[0];
        continue;
      }
      // 目前这个物品重量超过背包容量j 肯定不能放 dp[i][j] = dp[i -1][j]
      if (a > j) {
        dp[i][j] = dp[i -1][j]
      } else {
        // 放这个物品或者不放这个物品 dp[i -1][j] || dp[i - 1][j - a ]
        dp[i][j] = dp[i -1][j] || dp[i - 1][j - a ]
      }
    }
  }
  return dp[nums.length - 1][target]
}