Java short DP solution with explanation

• If sum of all the numbers is odd, the surely we cannot reach equal partition.

Using a boolean dp array (limit its max index to sum/2) whose ith entry indicates there is a way to reach the value i using certain subset of the numbers. SO if at any time we can find a subset to reach sum/2 index, we are able to equally partition.

``````   public boolean canPartition(int[] a) {
int sum = 0;
for(int n:a){
sum += n;
}
if(sum%2>0)
return false;

boolean []dp = new boolean[sum/2+1];
dp[0]=true; // empty array
int max=0;
for(int n: a){
if(n>sum/2)
return false;  // single number making bigger than sum/2 no way equal partition.
for(int j = 0; j<=max; j++){
if(dp[j] && ((j+n) <= sum/2) ){
dp[j+n] = true;
max = Math.max(max, j+n);
if(max==sum/2)
return true;
}
}
}
return dp[sum/2];
}``````

• I don't think your solution can pass the test case [1, 2, 5].

My is as follows, which is similar to yours:

``````public class Solution {
public boolean canPartition(int[] nums) {
if(nums.length <= 1) return false;
int sum = 0;
for(int num: nums){
sum += num;
}
if(sum % 2 == 1) return false;

boolean[] dp = new boolean[sum/2+1];
dp[0] = true;

int end = 0;
for(int num: nums){
if(num > sum/2) return false;

for(int i = end; i>=0; i--){
if(dp[i] && (i+num) <= sum/2){
dp[i+num] = true;
end = end > i+num ? end : i+num;
if(end == sum/2) return true;
}
}
}

return dp[sum/2];
}
}

``````

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