分割等和子集（01背包的变种）-416

[sl1673495]

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

注意:

每个数组中的元素不会超过 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 背包问题，要想清楚如果数组可以分割成两个相等的数组，那么我们的目标其实是求有没有子数组的和为「整个数组的和的一半」（下文称为 target）。而由于这个和是「整个数组」的值加起来的一半求得的，所以其中的一半我们找到了，此时另外的子数组相加的值一定也是一半，也就是 target。

只要想清楚这个问题，题目就迎刃而解了。

这里的二维 DP 表：

纵坐标 i 代表数组中覆盖到的元素，从第一个元素开始（ i = 2 是包含了 i = 1 和 i = 0 的情况的。）。

横坐标 j 代表 [0...target] 中的值 j 是否可以由 i 覆盖到的数值凑得，它是 true 或 false。

每一步也分为「拿当前的元素」和「不拿当前的元素」。

1. 拿的话，结果就变为 dp[i - 1][j - nums[i]] （看看用前几个数能不能凑成「目标值 - 当前的值」）。
2. 不拿的话，结果就变为 dp[i - 1][j] （不用这个数，前几个数能不能凑成当前的值）
3. 特殊情况，当前的值可以直接凑成目标值，也算 true。

只要这三项中有任意一项为 true，那么结果就为 true。

另外有几个注意点：

1. 一开始就可以判断，数组之和除以二后不是整数的话，直接失败。因为这一定不可能是两个整数子数组相凑的结果。
2. 只要用任意数量的子数组可以拼凑出来 target 的值，也就是 dp 数组的任意一层的最右边的值计算出是 true，那么整题的结果就为 true。因为不论你用几个值凑出了 target 值，哪怕只用了一个值。另外剩下的值之和一定也是 target。

说实话这篇题解讲的更好：

https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/0-1-bei-bao-wen-ti-xiang-jie-zhen-dui-ben-ti-de-yo/

题解

/**
 * @param {number[]} nums
 * @return {boolean}
 */
let canPartition = function (nums) {
  let n = nums.length

  let sum = nums.reduce((a, b) => a + b);

  let target = sum / 2;

  // 数据不是整数 直接return
  if (Math.ceil(target) !== target) {
    return false;
  }

  let dp = new Array(n);
  for (let i = 0; i < dp.length; i++) {
    dp[i] = new Array(target + 1).fill(false);
  }

  // 列代表可以选择去凑数的数值
  for (let i = 0; i < dp.length; i++) {
    // 行代表是否可以凑到这个数字j
    for (let j = 0; j <= target; j++) {
      // 不用当前数，直接选择前一行的结果
      let pickPrev = (dp[i - 1] ? dp[i - 1][j]: false) || false

      // 拿出当前数，并且从前一行里找其他的值能否凑成剩下的值
      let pickCurrentAndPrev = (dp[i - 1] ? dp[i - 1][j - nums[i]]: false) || false

      // 只拿的值直接去凑目标值
      let pickCurrent = j === nums[i]

      // 任意一者满足 即可理解成 「i下标的值」配合「i下标之前的数值」 可以一起凑成目标值
      let can = (
        pickPrev ||
        pickCurrent||
        pickCurrentAndPrev
      )

      dp[i][j] = can

      // 只要任意一行的 target 列满足条件 即可认为有「子数组」可以凑成目标值 直接返回 true
      if ((j === target) && can) {
        return true
      }
    }
  }
  return dp[n - 1][target]
};