416. 分割等和子集

难度：🟡 Medium | 标签：动归、0-1 背包 | 状态：⬜ LeetCode 链接

思路

总和奇数直接 false。否则转 0-1 背包：能否从 nums 选出和为 sum / 2？

dp[j] 表示能否凑出和 j。dp[j] = dp[j] || dp[j - nums[i]]，j 从大到小（0-1 背包的关键）。

代码

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

复杂度

• 时间 O(n · sum/2)，空间 O(sum/2)

易错 / 回顾

• 0-1 背包 j 倒序；完全背包正序
• 总和奇数提前返回
• 进阶：能否拆 K 等份（698 题）→ 状压 DP