concise C++ dp solution


  • 1
    H
    class Solution {
    public:
        bool canPartition(vector<int>& nums) {
            int sum = accumulate(nums.begin(), nums.end(), 0);
            if(sum&1) return false;
            vector<int> dp(sum/2+1, 0);
            for(int i = 0, dp[0] = 1; i < nums.size(); i++)
            {
                for(int j = sum/2; j >= nums[i]; j--)
                    dp[j] = dp[j] || dp[j-nums[i]];
            }
            return dp[sum/2];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.