# JAVA DP and MEMO Recursive Solutions.

• my two solution's pre-prepare part is same, only find part is diff!
dp solution:
Runtime: 26 ms, beats 79.30% of java submissions.

``````public class Solution {
public boolean canPartition(int[] nums) {

if(nums.length<=1)
return false;
if(nums.length==2)
return nums[0]==nums[1];

int sum = 0;
for(int num: nums)
sum += num;

if(sum%2!=0) return false;
sum /= 2;

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

for(int i=0; i<nums.length; i++){
for(int j=sum; j>=nums[i]; j--)
dp[j] = dp[j] || dp[j-nums[i]];
}

return dp[sum];
}
}
``````

memo recursive solution:
Runtime: 19 ms, beats 93.69% of java submissions.

``````public class Solution {

Boolean[][] memo;

public boolean canPartition(int[] nums) {

if(nums.length<=1)
return false;
if(nums.length==2)
return nums[0]==nums[1];

int sum = 0;
for(int num: nums)
sum += num;

if(sum%2!=0) return false;
sum /= 2;

memo = new Boolean[nums.length+1][sum+1];
return rec(nums, 0, sum);
}

boolean rec(int[] nums, int start, int target){

if(start>=nums.length)
return target==0;
if(target==0)
return true;
if(target<0)
return false;

if(memo[start][target]!=null)
return memo[start][target];

memo[start][target] = rec(nums,start+1,target-nums[start]) ||  rec(nums, start+1, target);
return memo[start][target];
}

}
``````

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