This question was the first DP problem I learned and solved.


  • 0
    F

    It reminds me of the old times in school.

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

Log in to reply
 

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