416. 分割等和子集

第一眼不会

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // dp[i] 容量为s//2的01背包
        int sum = 0;
        for (int i = 0; i < nums.size(); i ++ ) {
            sum += nums[i];
        }
        if (sum & 1) return false;
        int target = sum >> 1;
        vector<int> dp (1+target);
        for (int i = 0; i < nums.size(); i ++ ) {
            for (int j = target; j >= nums[i]; j -- ) {
                dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[target] == target;
    }
};

一下子想不出转换成01背包的想法