c++ solution with dynamic programming


  • 0
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (auto i : nums) 
    	sum += i;
        if (sum % 2)
    	return false;
        // dp[i][j] == true iff there is a subset of the first j numbers such that the sum of the subset is i
        bool dp[sum/2+1][nums.size()+1];
        for (int i = 0; i < sum/2 + 1; i++) {
    	for (int j = 0; j < nums.size() + 1; j++) {
    	    dp[0][j] = true; // sum of an empty set is 0
    	    dp[i][0] = false; // numbers are positive
    	}
    	dp[0][0] = true;
        }
    
        for (int i = 1; i < sum/2 + 1; i++)
    	for (int j = 1; j < nums.size() + 1; j++)
                // we either take the last element or don't
    	    dp[i][j] = (i > nums[j-1]) && (dp[i][j-1] || dp[i - nums[j-1]][j-1]);
    
        return dp[sum/2][nums.size()];
    

  • 1

    For the second part of this linedp[i][j] = dp[i][j-1] || dp[i - nums[j-1]][j-1]; I think you'd better add the conditionif(i >= nums[j - 1]) to check if i - nums[j - 1] is valid.


  • 0

    @xietao0221 You are absolutely right!


  • 1
    B

    my solution with Dp is easy to understand.

    class Solution {
    public:
    bool canPartition(vector<int>& nums) {

       int sum = 0;
       
       for(int i=0; i<nums.size(); i++) sum += nums[i];
       
       if( sum & 0x01 ) {  return false; }
       
       int target = sum >> 1;
       
       vector<bool> res(target+1, 0);
       //printf("target = %d", target);
    
       res[0]  = true;
       
       for(int i=1; i<=target; i++)
       {
           for(int j=0; j<nums.size(); j++)
           {
               if(nums[j] <= i  && !res[i] ) res[i] = res[i-nums[j]];
           }
       }
       
       return res[target];
        
    }
    

    };


  • 0
    Z

    @blueday0594
    Your source will fail in the case [2, 6].
    In this case, target is 4. You source will return res[4] == true using 2 + 2.
    However, the expected answer is false.


Log in to reply
 

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