分割等和子集

🟡 Medium · 🏷️ 数组、动态规划（0/1 背包） · LeetCode#416

📖 题目

判断数组能不能分成两个元素和相等的子集。

💡 思路

两个子集互补且和相等，意味着每个子集的和都是 sum/2——如果 sum 是奇数，直接不可能，返回 False。

问题转化成：能不能从数组里选若干个数，刚好凑出 target = sum // 2？这是零钱兑换那种背包问题的另一个变体，区别是每个数字只能用一次（0/1 背包），零钱兑换的硬币可以无限用（完全背包）。

dp[j] 表示"能不能凑出金额 j"（布尔值）。对每个数字 num：dp[j] = dp[j] or dp[j-num]——不选这个数已经能凑出，或者选了这个数刚好能凑出，两种情况有一种成立就行。

关键是内层要倒序遍历：如果正序遍历，dp[j-num] 读到的可能是这一轮已经更新过的值，相当于同一个数被用了两次；倒序遍历保证读到的是"还没处理这个数之前"的状态，天然保证每个数只用一次。

💻 代码

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)，空间复杂度 O(target)。正序遍历（物品能重复用）还是倒序遍历（物品只用一次），是完全背包和 0/1 背包在代码上唯一的区别。