LeetCode416：分割等和子集

题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

解题思想

    [1,5,11,5]   和为22，其中一半为 11。如果能寻找到若干数的和为11则成立
    
    可以抽象为一个0-1背包问题：容量为11的背包能否被装满
    上述的数组可以看作 重量和价值等同


    dp[j]：容量为j的背包最大价值dp[j]

    递推公式：dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
    本题：dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])

    遍历顺序：
        for (int i = 0; i < n; i++)
            //背包倒序遍历
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
           }

代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int target = 0;
        for (auto a : nums) target += a;
        if (target % 2 != 0) return false;
        target /= 2;

        int n = nums.size();
        vector<int> dp(target+1, 0);
        for (int i = 0; i < n; i++)
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        return dp[target] == target;
    }
};