分割等和子集

题目描述

LeetCode 416 — 分割等和子集 (Medium)

给你一个只包含正整数的非空数组 nums。请判断能否将数组分成两个子集，使两个子集的元素和相等。每个元素只能属于其中一个子集。

示例 1：

• 输入：nums = [1,5,11,5]
• 输出：true
• 解释：可以分成 [1, 5, 5] 和 [11]，两部分的和都是 11。

示例 2：

• 输入：nums = [1,2,3,5]
• 输出：false
• 解释：数组不能分成两个元素和相等的子集。

约束：

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

---

求解思路：动态规划

如果数组总和是奇数，就不可能平均分成两份，可以直接返回 false。当总和为偶数时，问题变成：能否从数组中挑出若干个数，使它们的和恰好等于总和的一半 target。另一部分自然也会是 target。

这可以看成 0/1 背包的可达性问题：每个数字是一个只能使用一次的物品，状态 dp[j] 表示是否能用已经处理过的数字凑出和 j。初始时不选任何数字就能凑出 0，因此 dp[0] 为真。处理一个数字 num 时，容量 j 可以不选它，沿用原来的 dp[j]；也可以选它，前提是之前能凑出 j - num，于是转移为 dp[j] || dp[j - num]。

容量必须从大到小更新。若从小到大更新，刚由当前 num 得到的状态会继续参与本轮计算，相当于同一个数字被重复使用；倒序遍历则保证 dp[j - num] 仍代表没有使用当前数字前的状态。最后检查 dp[target] 即可。

解法：一维 0/1 背包

/*
和必须为偶数才能分割
算出和，然后套0/1背包模型，最后看能不能凑出总和为sum/2
设 dp[i] 表示是否存在能凑出和为 i 的子集
dp[i] = dp[i - num] || dp[i]
*/

#include <vector>

using namespace std;

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        if(sum % 2 == 1){
            return false;
        }
        int target = sum / 2;
        vector<int> dp(target + 1,0);
        dp[0] = 1;
        for(int num : nums){
            for(int j = target; j >= num; j--){
                dp[j] = dp[j] || dp[j - num];
            }
        }
        if(dp[target] == 1) return true;
        else return false;
    }
};

复杂度： 时间 $O(n \cdot target)$，其中 target 是数组总和的一半；空间 $O(target)$。

---

相关题目

• LeetCode 494 — 目标和（背包状态计数）
• LeetCode 1049 — 最后一块石头的重量 II（尽量将总和分成接近的两部分）
• LeetCode 518 — 零钱兑换 II（完全背包计数）
• LeetCode 322 — 零钱兑换（完全背包求最小值）