416.分割等和子集

分割等和子集

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

示例 1：

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

示例 2：

输入：nums = [1,2,3,5]
输出：false

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

解析

转化为 0-1 背包问题：能否从数组中选出一些数，使其和等于总和的一半。

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  const sum = nums.reduce((a, b) => a + b, 0);
  if (sum % 2 !== 0) return false;

  const target = sum / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;

  for (const num of nums) {
    // 从后往前遍历，防止重复使用同一个元素
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }
  return dp[target];
};

经典 0-1 背包的空间优化版本。时间复杂度 O(n * target)，空间复杂度 O(target)。