# easy dp java solution, with a problem waiting to solve

• refer on https://discuss.leetcode.com/topic/76243/java-15-ms-c-3-ms-o-ns-iterative-dp-solution-using-subset-sum-with-explanation, thx @yuxiangmusic, your explanation is detailed. However, there is a question, if I replace the "return dp[s] != 0;" by "dp[s] > 0", the answer is wrong.

public class Solution {
public boolean canPartition(int[] nums) {
if(nums == null || nums.length == 0)
return false;
int sum = 0;
for(int num : nums)
sum += num;
if(sum % 2 != 0)
return false;
int s = sum / 2;
int[] dp = new int[s + 1];
dp[0] = 1;
for(int num : nums){
for(int j = s; j >= num; j--){
dp[j] += dp[j - num];
}
}
return dp[s] != 0; //if replaced by  dp[s] > 0 => wrong
}
}

• Negative result is caused by int overflow

For example, if nums contains 200 1's and we want a subset sum of 100, then the result choose(200, 100) = 9.0548515e+58 will definitely overflow for int and long as well

• Thank you! I agree with this explanation.

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