Leetcode-in-JavaScript

# [416] 分割等和子集

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

注意：

每个数组中的元素不会超过 100

数组的大小不会超过 200

示例 1:

输入：[1, 5, 11, 5]

输出：true

解释：数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入：[1, 2, 3, 5]

输出：false

解释：数组不能分割成两个元素和相等的子集。

这道题看上去比较棘手，容易掉入求和比较误区。

但实际上，我们将题目转换一下说法：从该长度为 N 的数组中取出若干元素，使得其和为 sum / 2（sum 为原数组的和）。是不是就能很快地看出考察的重点了呢？

没错，就是动态规划分类中一个典型案例—— 0-1 背包问题：每一个元素不可分割，且对于每一个元素，只有取或者不取两个选项，并且最终获得的和等于或不超过某个定值。

知道了考点是动态规划，那么就能直接考虑状态转移方程了。状态转移方程首先要明确状态和选择两点。在本题中，显然选择是数组中的数字，而状态就是已选择的数字和是否等于 sum / 2 了。

由此我们定义出 dp 数组：dp[i][j] 表示，对于前 i 个物品，是否能将容量为 j 的背包恰好装满。

列出状态转移方程：

  1. 若当前物品容量超过了背包总容量，则不能取当前物品，与能选前 i-1 个物品的结果一致
  2. 若能取当前物品，则有两种情况，一种是不取当前物品，则与能选前 i-1 个物品的结果一致，若取当前物品，则判断当前物品 i 是否正好能装满取之前的背包剩余容量 j - nums[i - 1]

接下来考虑边界条件，

  1. 题目已知数组中只包含正整数，因此，sum / 2 不为整数的可以直接 pass 掉。
  2. 当背包容量为 0 时，任何情况都能满足要求（即不装任何东西）。
  3. 当数组长度为 0 时，任何情况都不能满足要求。

就此可以输出代码。

function canPartition(nums: number[]): boolean {
  const sum = nums.reduce((curr, prev) => curr + prev);
  if (sum % 2 !== 0) return false;

  const target = sum / 2;
  const len = nums.length;

  const dp: boolean[][] = Array(len + 1)
    .fill(0)
    .map(x => Array(target + 1).fill(false));

  // 当背包容量为 0 时，任何情况都能满足要求（不装）
  for (let i = 0; i <= len; i++) {
    dp[i][0] = true;
  }

  for (let i = 1; i <= len; i++) {
    for (let j = 1; j <= target; j++) {
      if (j < nums[i - 1]) {
        // 当前物品容量超过了背包总容量，则不能取当前物品，与选前 i-1 个物品的结果一致
        dp[i][j] = dp[i - 1][j];
      } else {
        // 若能取，则分为两种情况
        // 一种是不取当前物品，则与能选前 i-1 个物品的结果一致
        // 若取当前物品，则判断当前物品 i 是否正好能装满取之前的背包剩余容量 j - nums[i - 1]
        // 有一种情况为 true，当前结果都为 true
        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
      }
    }
  }
  return dp[len][target];
}

我们还能为优化空间复杂度做出一些努力。可以看出，dp[i][j] 的状态转移方程都是通过 dp[i-1] 中的对应的值算出来的，因此每一次遍历都只用到了上一行的计算结果，因此我们就能将二维的 dp 数组降为一维，从而优化空间复杂度。

这里需要注意的是，因为遍历时用到的依赖为上一行的左侧的值，因此在改为一维数组后，对 j 的遍历方向一定要从右向左，这样才能保证上一行左侧的值不被当前行遍历所覆盖。

function canPartition(nums: number[]): boolean {
  const sum = nums.reduce((curr, prev) => curr + prev);
  if (sum % 2 !== 0) return false;

  const target = sum / 2;
  const len = nums.length;

  const dp: boolean[] = Array(target + 1).fill(false);

  // 当背包容量为 0 时，任何情况都能满足要求（不装）
  dp[0] = true;

  for (let i = 1; i <= len; i++) {
    for (let j = target + 1; j > 0; j--) {
      if (j >= nums[i - 1]) {
        // 若当前物品容量没有超过背包总容量，则分为两种情况
        // 一种是不取当前物品，保持原样
        // 若取当前物品，则判断当前物品 i 是否正好能装满背包剩余容量 j - nums[i - 1]
        // 有一种情况为 true，当前结果都为 true
        dp[j] = dp[j] || dp[j - nums[i - 1]];
      }
    }
  }
  return dp[target];
}

← [474] 一和零 →