leetcode 416 分割等和子串

class Solution {
public:
    bool canPartition(vector& nums) {
        //因为题目要求时分割成两个子集，并且两个子集的和相等
        int sum=0;
        vectordp(10001,0);//dp[i]表示容量为i，最大可以凑成i的子集之和为dp[i]
        for(int i=0;i< nums.size(); i++){
            sum+=nums[i];           //计算总和
        }
        if(sum % 2 == 1)return false;//无解
        int targer = sum / 2;           //如果背包可以凑成的子集之和等于数组元素之和的一半说明有解
        //开始01背包
        for(int i=0;i < nums.size(); i++){
            for(int j= targer;j >= nums[i]; j--){//确保每一个元素不可重复
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);//取与不取
            }
        }
        if(dp[targer]==targer)return true;
        return false;
    }
};