c dp solution time o(n*m) space o(m)


  • 0
    H
    bool canPartition(int* nums, int numsSize) {
        int s=0;
        for(int i=0;i<numsSize;i++)
            s+=nums[i];
        if(s%2)
            return false;
        s=s/2;
        int* dp=malloc(sizeof(int)*(s+1));
        if(nums[0]<=s)
            dp[nums[0]]=1;
        for(int i=1;i<numsSize;i++){
            for(int j=0;j<=s;j++){
                if(dp[j]==1&&j+nums[i]<=s)
                    dp[j+nums[i]]=1;
            }
            if(nums[i]<=s)
                dp[nums[i]]=1;
        }
        return dp[s];
    }
    

Log in to reply
 

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