分割等和子集

Tips

题目类型: Dynamic Programming

背包问题汇总

题目

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

示例

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

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

题解

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

JavaScript - 二维数组

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

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

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

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

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

  return dp[n][capacity]
}

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

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

JavaScript - 一维数组

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

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  let capacity = nums.reduce((acc, val) => acc + val)
  if (capacity % 2 === 1) return false
  const n = nums.length
  capacity /= 2

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

  for (let i = 0; i < n; i++) {
    for (let w = capacity; w >= nums[i]; w--) {
      dp[w] = dp[w] || dp[w - nums[i]]
    }
  }

  return dp[capacity]
}

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

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

Rust

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

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

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

    dp[n][capacity as usize]
}