0416. Partition Equal Subset Sum ================================ 题目信息 -------- :题号: 0416 :难度: Medium :主题: 正整数数组、两个子集、元素全覆盖、等和判断 :原题: `LeetCode 0416 `_ :重点: 每个数组位置恰好属于一个子集、两个子集元素和必须相同、相同数值的不同位置分别使用 题目重述 -------- 给定只包含正整数的数组 ``nums``,判断能否把全部数组元素划分成两个子集,使两个子集的元素和相等。 ``nums.length`` 位于 ``[1, 200]``,每个元素位于 ``[1, 100]``。数组中的每个位置必须恰好分配给一个子集,不能遗漏或重复使用;重复数值位于不同下标时仍是不同的元素实例。函数只返回是否存在这样的划分,不需要返回具体子集。 自建示例 -------- 存在等和划分: .. code-block:: text 输入:nums = [2, 3, 5] 输出:true 解释:可以划分为 [5] 和 [2,3],两个子集的元素和都为 5。 总和为偶数仍可能无法划分: .. code-block:: text 输入:nums = [2, 2, 3, 5] 输出:false 解释:总和为 12,但不存在元素和恰好为 6 的子集,因此无法分成两个等和部分。 只寻找一半总和 ---------------- 若所有元素总和为奇数,直接不可能平分;若为偶数,只需判断是否存在一个子集的和为 ``total / 2``,剩余元素就自动构成另一半。令 ``dp[s]`` 表示处理过的元素中是否能组成和 ``s``,每加入一个数时从目标和向下更新,确保同一个数组位置不会在同一轮被重复使用。 C++ 实现 -------- .. code-block:: cpp class Solution { public: bool canPartition(std::vector& nums) { int total = std::accumulate(nums.begin(), nums.end(), 0); if (total % 2 != 0) return false; int target = total / 2; std::vector 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)``。