TNotes.leetcode

Appearance

0416. 分割等和子集【中等】

0416. 分割等和子集【中等】 ​

1. 📝 题目描述 ​

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

示例 1：

txt
输入：nums = [1, 5, 11, 5]
输出：true

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

示例 2：

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

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

提示：

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

2. 🎯 s.1 - 0-1 背包 DP ​

c
bool canPartition(int* nums, int numsSize) {
    int sum = 0;
    for (int i = 0; i < numsSize; i++) sum += nums[i];
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    bool* dp = (bool*)calloc(target + 1, sizeof(bool));
    dp[0] = true;
    for (int i = 0; i < numsSize; i++) {
        for (int j = target; j >= nums[i]; j--) {
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    bool res = dp[target];
    free(dp);
    return res;
}
js
/**
 * @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 Uint8Array(target + 1)
  dp[0] = 1
  for (const num of nums) {
    for (let j = target; j >= num; j--) {
      dp[j] |= dp[j - num]
    }
    // if (dp[target] === 1) return true // 可提前退出
  }
  return false
}
py
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        if s % 2 != 0:
            return False
        target = s // 2
        dp = [False] * (target + 1)
        dp[0] = True
        for num in nums:
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]
        return dp[target]
  • 时间复杂度：O(n×target)，其中 target=sum/2
  • 空间复杂度：O(target)

算法思路：

  • 问题转化为：能否从数组中选出若干数使其和恰好为 sum/2
  • 经典 0-1 背包，dp[j] 表示是否能凑出和 j
  • 状态转移：dp[j]=dp[j]||dp[j−nums[i]]
    • dp[j] 表示集合中不选当前数 nums[i] 时 j 已可达
    • dp[j−nums[i]] 表示选当前数 nums[i] 时 j 已可达
    • dp[j] 只允许从 0 -> 1 不允许 1 -> 0
  • 倒序遍历：保证每个数只被使用一次，防止重复使用

3. 🎯 s.2 - bitset 优化 ​

c
bool canPartition(int* nums, int numsSize) {
    int sum = 0;
    for (int i = 0; i < numsSize; i++) sum += nums[i];
    if (sum % 2 != 0) return false;
    int target = sum / 2;

    // 位集：157 个 64 位字可表示 0~10047 共 10048 个位（target 最大为 10000）
    unsigned long long bits[157];
    memset(bits, 0, sizeof(bits));
    bits[0] = 1ULL; // bit 0 置 1，表示和 0 可达

    for (int i = 0; i < numsSize; i++) {
        int num = nums[i];
        int wshift = num / 64; // 整字偏移
        int bshift = num % 64; // 位内偏移
        // 从高位到低位更新，避免重复使用同一个数
        for (int w = 156; w >= wshift; w--) {
            unsigned long long val = bits[w - wshift] << bshift;
            if (bshift > 0 && w > wshift) {
                val |= bits[w - wshift - 1] >> (64 - bshift);
            }
            bits[w] |= val;
        }
    }
    return (bits[target / 64] >> (target % 64)) & 1ULL;
}
js
/**
 * @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

  let bits = 1n // BigInt，dp[0] = 1
  for (const num of nums) {
    bits |= bits << BigInt(num)
  }
  return (bits >> BigInt(target)) & 1n
}
py
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        target = total // 2
        bits = 1  # bit 0 置 1，表示和 0 可达
        for num in nums:
            bits |= bits << num
        return bool((bits >> target) & 1)
  • 时间复杂度：O(n×⌈target/64⌉)，用位运算一次处理 64 个 DP 状态，相比 0-1 背包有约 64 倍常数优化
  • 空间复杂度：O(⌈target/64⌉)，固定大小的位集替代布尔数组

算法思路：

  • 用一个大整数 bits 模拟位集，第 i 位为 1 表示和 i 可达，初始 bits = 1（只有第 0 位为 1）
  • 对每个数 num 执行 bits |= bits << num：将所有已可达的和加上 num，一次位运算即可覆盖 64 个 DP 状态的更新
  • 最终检查第 target 位是否为 1

Discussions