416

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int num:nums) sum += num;
        if(sum&1) return false;

        sum /= 2;
        vector<bool> dp(sum+1, false);
        dp[0] = true;
        for(int num:nums){
            for(int j=sum; j>=num; j--)
                dp[j] = (dp[j] || dp[j-num]);
        }
        return dp[sum];
    }
};