分割等和子集

Tips

题目类型: Dynamic Programming

题目

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

示例

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

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

题解

这道题可以转化成 0-1 背包问题. 先给 nums 求和记为 weight, 因此这道题就变成了: 给你背包容量为 weight / 2 和 n 个物品, 每个物品的重量为 nums[i], 现在让你装物品, 是否存在一种装法, 能够恰好将背包装满.

JavaScript - 二维数组

二维数组解法

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  let weight = nums.reduce((acc, val) => acc + val)

  // 如果和为奇数, 肯定无法切割成两个子数组
  if (weight % 2 === 1) return false
  weight /= 2

  const n = nums.length
  const dp = new Array(n + 1)
    .fill(false)
    .map(() => new Array(weight + 1).fill(false))

  // 重量为 0 时选择 0 个数字, 一定是 true
  dp[0][0] = true

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= weight; j++) {
      if (j - nums[i - 1] < 0) {
        // 背包容量不足, 不能装入第 i 个物品
        dp[i][j] = dp[i - 1][j]
      } else {
        // 装入或不装入背包
        // 不装入: dp[i - 1][j]
        // 装入: 如果装了第 i 个物品, 就要看背包的剩余重量 j - nums[i - 1] 限制下是否能够被恰好装满
        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]
      }
    }
  }

  return dp[n][weight]
}

• 时间复杂度: O(n * weight), 其中 n 是数组 sum 的长度, weight 是数组元素和的一半.

• 空间复杂度: O(target * weight), 其中 n 是数组 sum 的长度, weight 是数组元素和的一半.

JavaScript - 一维数组

dp[i][j] 都是通过上一行 dp[i - 1][..] 转移过来的, 之前的数据都不会再使用了, 因此可以把 i 消去.

var canPartition = function (nums) {
  let weight = nums.reduce((acc, val) => acc + val)
  if (weight % 2 === 1) return false
  const n = nums.length
  weight /= 2

  const dp = new Array(weight + 1).fill(false)
  dp[0] = true

  for (let i = 1; i <= n; i++) {
    for (let j = weight; j >= nums[i - 1]; j--) {
      dp[j] = dp[j] || dp[j - nums[i - 1]]
    }
  }

  return dp[weight]
}

• 时间复杂度: O(n * weight), 其中 n 是数组 sum 的长度, weight 是数组元素和的一半.

• 空间复杂度: O(target).

Rust

pub fn can_partition(nums: Vec<i32>) -> bool {
    let n = nums.len();
    let mut weight = nums.iter().sum::<i32>();
    if (weight % 2 == 1) {
        return false;
    }
    weight /= 2;

    let mut dp = vec![vec![false; (weight + 1) as usize]; n + 1];
    dp[0][0] = true;

    for i in 1..=n {
        for j in 1..=(weight as usize) {
            if (j as i32) - nums[i - 1] < 0 {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][((j as i32) - nums[i - 1]) as usize];
            }
        }
    }

    dp[n][weight as usize]
}