Leetcode 416

题目要求

给定一个整数数组，试求其是否能划分为2个和相等的子集

核心算法和原理

• 即求是否能从这个集合中选出一个子集的和为 sum / 2（sum为奇数直接返回false）

• 类似DP中的背包问题：每个背包重量为nums[i]，求是否存在一个总重量为sum / 2的选择方案

• 维数优化：直接省去i这个维度，但是注意w要从后往前遍历，因为需要使用「 在i迭代前的dp[w - nums[i - 1] 」，相应的dp[nums[i]]也是在后面更新

代码

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

                if (x <= sum / 2)   dp[x] = true;
                if (dp[sum / 2]) {return true;}
            }
            return false;
        }

    }
};