JAVA DP and MEMO Recursive Solutions.


  • 1
    T

    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];
        }
        
    
    }
    

Log in to reply
 

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