0416. Partition Equal Subset Sum

题目信息

题号:

0416

难度:

Medium

主题:

正整数数组、两个子集、元素全覆盖、等和判断

原题:

LeetCode 0416

重点:

每个数组位置恰好属于一个子集、两个子集元素和必须相同、相同数值的不同位置分别使用

题目重述

给定只包含正整数的数组 nums,判断能否把全部数组元素划分成两个子集,使两个子集的元素和相等。

nums.length 位于 [1, 200],每个元素位于 [1, 100]。数组中的每个位置必须恰好分配给一个子集,不能遗漏或重复使用;重复数值位于不同下标时仍是不同的元素实例。函数只返回是否存在这样的划分,不需要返回具体子集。

自建示例

存在等和划分:

输入:nums = [2, 3, 5]
输出:true
解释:可以划分为 [5] 和 [2,3],两个子集的元素和都为 5。

总和为偶数仍可能无法划分:

输入:nums = [2, 2, 3, 5]
输出:false
解释:总和为 12,但不存在元素和恰好为 6 的子集,因此无法分成两个等和部分。

只寻找一半总和

若所有元素总和为奇数,直接不可能平分;若为偶数,只需判断是否存在一个子集的和为 total / 2,剩余元素就自动构成另一半。令 dp[s] 表示处理过的元素中是否能组成和 s,每加入一个数时从目标和向下更新,确保同一个数组位置不会在同一轮被重复使用。

C++ 实现

class Solution {
public:
    bool canPartition(std::vector<int>& nums) {
        int total = std::accumulate(nums.begin(), nums.end(), 0);
        if (total % 2 != 0) return false;
        int target = total / 2;
        std::vector<bool> dp(target + 1, false);
        dp[0] = true;

        for (int value : nums) {
            for (int sum = target; sum >= value; --sum) {
                dp[sum] = dp[sum] || dp[sum - value];
            }
        }
        return dp[target];
    }
};

代码分析

倒序枚举和,保证当前元素只参与一次;dp[0] 表示尚未选择元素的空子集,正整数约束使状态方向清晰。总和为 S 时,时间复杂度为 O(nS),额外空间为 O(S)。