Java short DP solution with explanation


  • 3
    M

    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.

    Disclaimer: logic borrowed from https://chinmaylokesh.wordpress.com/2011/02/10/balanced-partition-problem-finding-the-minimized-sum-between-two-partitions-of-a-set-of-positive-integers/

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

  • 2
    N

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

Log in to reply
 

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