分割等和子集

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

注意:

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

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

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

我们需要对这个问题做一个等价转换。题目问我们：在输入数组中是否存在一个子集（子集非空，且每个元素至多只能选择一次），子集中所有元素的和为输入数组所有元素的和的一半。

这其实是一个典型的「0-1 背包问题」，我们将题目的条件和问的结果与「0-1 背包问题」的联系画出表格如下。

一个比较容易判断的前提条件：如果输入数组所有元素的和为奇数，一定找不到这样的子集
注意：

• 当前问题要求背包 恰好能够装满 总重量为 j 的背包，需要注意初始化的条件：nums[0] 只能填满容积为 nums[0] 的背包
• 以后我们在求解这类问题的时候，一定要区分清楚「恰好能够装满」和「装入容量不超过 **j** 的背包」的区别，我们在后面的例题中还会和大家强调这样的细节

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  // 求所有数的总和
  let sum = nums.reduce((acc, num) => acc + num);
  if (sum % 2 !== 0) {
    return false;
  }
  const len = nums.length;
  const target = sum / 2;
    // dp[i][j]：前缀区间 [0..i] 里是否有一部分元素的和恰好为 j
  const dp = Array.from(nums).map(() =>
    new Array(target + 1).fill(false)
  );
    // 初始化：nums[0] 只能填满容积为 nums[0] 的背包
    if (nums[0] <= target) {
        dp[0][nums[0]] = true;
    }
    for (let i = 1; i < len; i++) {
      for (let j = 0; j <= target; j++) {
        if (nums[i] > j) {
        // 不选：把上一行照抄下来
          dp[i][j] = dp[i - 1][j];
        } else {
        // 选：二者之中有一个为 true 即可
          dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
        }
      }
    }
    return dp[len - 1][target];
};

空间优化

1. 根据「0-1 背包」问题表格复用的优化方法，我们可以采用「逆序填表」的方式将空间复杂度优化到 O(target)

   var canPartition = function (nums) {
   const sum = nums.reduce((acc, num) => acc + num);
   if (sum % 2 !== 0) return false;
   const target = sum / 2;
   const len = nums.length;
   const dp = new Array(target + 1).fill(false);
   dp[0] = true;
   for (let i = 0; i < len; i++) {
    for (let j = target; j >= nums[i]; j--) {
      if (dp[target]) return true // 提前返回结果
      dp[j] = dp[j] || dp[j - nums[i]];
    }
   }
   return dp[target];
   };