分割等和子集（大数优化版）

题目描述

给定一个只包含正整数的数组 nums，判断能否将数组分成两个子集，使得两个子集的元素和相等。

等价转化：

设数组总和为 total。若存在一个子集和为 total / 2，则剩下的元素和也为 total / 2，两边相等。

因此问题转化为：能否从 nums 中选出一个子集，使其和恰好等于 total / 2。

核心思路

总和为奇数：无法平分，直接返回 False；
总和为偶数：令 target = total / 2，问题变成 0-1 背包：每个数只能选一次，能否恰好凑出 target。

两种实现：

普通一维 DP：dp[s] 表示能否凑出和 s，内层倒序遍历；
bitset 优化：把 dp 看成一个二进制数，第 s 位为 1 表示和 s 可达，用位运算批量转移。

方法一：一维 0-1 背包 DP

思路及解法

定义 dp[s] 表示「能否从已遍历的数中选出一个子集，其和恰好为 s」。

初始 dp[0] = True（一个都不选，和为 0）；
对每个数 x，倒序遍历 s 从 target 到 x：
- dp[s] = dp[s] or dp[s - x]；
最终返回 dp[target]。

为什么倒序：0-1 背包中每个数只能用一次。正序遍历时 dp[s - x] 可能已被本轮更新，相当于同一个数用了多次。

代码

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2:
        return False

    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for x in nums:
        for s in range(target, x - 1, -1):
            dp[s] = dp[s] or dp[s - x]

    return dp[target]

复杂度分析

时间复杂度： $O(n \cdot target)$ ，其中 $n$ 是数组长度， $target = sum / 2$ 。
空间复杂度： $O(target)$ 。

适用场景

target 不太大时（例如 $\le 10^5$ ）可以稳定通过；target 很大时 Python 循环会超时。

方法二：bitset 优化（推荐）

思路及解法

把 dp 看成一个二进制整数：

第 s 位为 1 表示「和 s 可达」；
初始 bits = 1，只有第 0 位是 1；
加入数字 x 时，bits << x 表示「原来所有可达和都加上 x」；
bits |= bits << x 等价于 dp[s] = dp[s] or dp[s - x] 的批量操作。

限制位数：用 mask = (1 << (target + 1)) - 1 截断到 target 位，避免整数无限增长。

答案：检查 bits 的第 target 位是否为 1。

代码

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2:
        return False

    target = total // 2
    bits = 1
    mask = (1 << (target + 1)) - 1

    for x in nums:
        if x > target:
            continue
        bits = (bits | (bits << x)) & mask

    return ((bits >> target) & 1) == 1

复杂度分析

时间复杂度： $O(n \cdot target / w)$ ，其中 $w$ 是机器字长（Python 大整数按字处理，实际远快于逐位循环）。
空间复杂度： $O(target / w)$ 。

适用场景

target 较大时明显优于普通 DP，是本题在大数据下的推荐写法。

原始代码 70% 通过率的原因分析

用户原始代码：

class Solution:
    def IsPartition(self, nums):
        sumall = sum(nums)
        if sumall % 2 != 0:
            return False
        target = sumall // 2
        n = len(nums)
        nums.sort()
        dp = [False] * (target + 1)
        dp[0] = True
        for x in nums:
            for j in range(target, x - 1, -1):
                dp[j] = dp[j] or dp[j - x]
        return dp[target]

DP 逻辑本身是正确的，总和奇数返回 False，否则倒序 0-1 背包判断 dp[target]。

通过率 70% 最可能来自两个非逻辑问题：

1. 输入读取方式

arr = list(map(int, input().split()))

只读取一行。如果后台数据：

多行输入；
带方括号、逗号（如 [1,5,11,5]）；
多组测试用例；

就会解析错误，导致部分用例失败。

改进：用 sys.stdin.read() 一次读完，并清洗掉 []、,：

import sys

data = sys.stdin.read().strip()
data = data.replace("[", " ").replace("]", " ").replace(",", " ")
arr = list(map(int, data.split()))

2. 普通一维 DP 在 `target` 较大时超时

O(n * target) 的 Python 双层循环在 target 达到 $10^5$ 甚至更大时容易 TLE。后台判题数据可能包含大 target 的用例。

改进：换成 bitset 写法，位运算批量转移，速度提升一个数量级。

3. 次要问题：`nums.sort()` 没必要

排序对 DP 正确性没有影响，可以删除。若想剪枝，可以在 x > target 时直接跳过。

完整可提交代码（核心代码模式）

只提交 class Solution 部分：

class Solution:
    def IsPartition(self, nums):
        total = sum(nums)
        if total % 2 != 0:
            return False

        target = total // 2
        bits = 1
        mask = (1 << (target + 1)) - 1

        for x in nums:
            if x > target:
                continue
            bits = (bits | (bits << x)) & mask

        return ((bits >> target) & 1) == 1

本地调试版（含输入解析）

import sys

class Solution:
    def IsPartition(self, nums):
        total = sum(nums)
        if total % 2 != 0:
            return False

        target = total // 2
        bits = 1
        mask = (1 << (target + 1)) - 1

        for x in nums:
            if x > target:
                continue
            bits = (bits | (bits << x)) & mask

        return ((bits >> target) & 1) == 1


if __name__ == "__main__":
    data = sys.stdin.read().strip()
    if data:
        # 兼容 [1,5,11,5] 和 1 5 11 5 两种格式
        data = data.replace("[", " ").replace("]", " ").replace(",", " ")
        arr = list(map(int, data.split()))
        print(Solution().IsPartition(arr))

测试用例

输入	输出	说明
`[1,5,11,5]`	`True`	`[1,5,5]` 和 `[11]`
`[1,2,3,5]`	`False`	总和 11 为奇数
`[2,2,3,5]`	`False`	总和 12，但凑不出 6
`[1,2,5]`	`False`	总和 8，凑不出 4
`[1,2,3]`	`True`	`[3]` 和 `[1,2]`

关键细节

1. 为什么总和奇数直接返回 False

两个子集和相等，则总和必须是偶数。奇数无法平分。

2. 为什么倒序遍历

0-1 背包每个数只能用一次。倒序遍历保证 dp[s - x] 是上一轮（未使用当前数）的状态。

3. bitset 中 `mask` 的作用

bits << x 会让可达和的范围向右扩展，若不截断，bits 会无限增长，浪费时间和空间。mask 只保留低 target + 1 位，超过 target 的和对答案没有意义。

4. `x > target` 时跳过

如果某个数本身大于 target，它不可能被选入和为 target 的子集，直接跳过，避免无意义位移。

5. 输入解析的兼容性

竞赛/笔试平台可能用空格分隔、换行分隔，甚至带 []、,。用 sys.stdin.read() 统一读取再清洗，最稳妥。

总结

问题转化：能否选出子集和为 sum / 2；
总和奇数：直接 False；
普通 DP：dp[s] = dp[s] or dp[s - x]，内层倒序，时间 $O(n \cdot target)$ ；
bitset：bits |= bits << x，时间大幅优化，大 target 首选；
70% 通过率：DP 逻辑正确，问题多半在输入读取和大数据超时；
通用套路：「能否凑出目标和」→ 0-1 背包；目标较大时用 bitset 优化。

分割等和子集（大数优化版）

分割等和子集（大数优化版）

题目描述

核心思路

方法一：一维 0-1 背包 DP

思路及解法

代码

复杂度分析

适用场景

方法二：bitset 优化（推荐）

思路及解法

代码

复杂度分析

适用场景

原始代码 70% 通过率的原因分析

1. 输入读取方式

2. 普通一维 DP 在 target 较大时超时

3. 次要问题：nums.sort() 没必要

完整可提交代码（核心代码模式）

本地调试版（含输入解析）

测试用例

关键细节

1. 为什么总和奇数直接返回 False

2. 为什么倒序遍历

3. bitset 中 mask 的作用

4. x > target 时跳过

5. 输入解析的兼容性

总结

相关题目

2. 普通一维 DP 在 `target` 较大时超时

3. 次要问题：`nums.sort()` 没必要

3. bitset 中 `mask` 的作用

4. `x > target` 时跳过