Java Dynamic Programming Solution (21ms, with explanation)


  • 7
    public boolean canPartition(int[] nums) {
    	int total = 0;
    	for(int i : nums) total+=i; // compute the total sum of the input array
    	if(total%2 != 0) return false; // if the array sum is not even, we cannot partition it into 2 equal subsets 
    	int max = total/2; // the maximum for a subset is total/2
    	int[][] results = new int[nums.length][max]; // integer matrix to store the results, so we don't have to compute it more than one time
    	return isPartitionable(max,0,0,nums,results);
    }
    
    public boolean isPartitionable(int max,int curr, int index, int[] nums, int[][] results) {
    	if(curr>max || index>nums.length-1) return false; // if we passed the max, or we reached the end of the array, return false
    	if(curr==max) return true; // if we reached the goal (total/2) we found a possible partition
    	if(results[index][curr]==1) return true; // if we already computed teh result for the index i with the sum current, we retrieve this result (1 for true)
    	if(results[index][curr]==2) return false; // if we already computed teh result for the index i with the sum current, we retrieve this result (2 for false)
    	boolean res = isPartitionable(max, curr+nums[index], index+1, nums, results) || isPartitionable(max, curr, index+1, nums, results); // else try to find the equal partiion, taking this element, or not taking it
    	results[index][curr] = res ? 1 : 2; // store the result for this index and this current sum, to use it in dynamic programming
    	return res;
    }
    

  • 1
    M

    Great solution. I am just trying to get a hand of DP. A quick question, why do we need a 2D array for this? Am I missing something? Can't we do it with a 1D array? I tried using your method and a 1D array and the solution still got accepted.

    public class Solution {
        public boolean canPartition(int[] nums) {
            if(nums==null || nums.length==0){
                return false;
            }
            int sum=0;
            for(int i=0; i<nums.length; i++){
                sum+=nums[i];
            }
            if(sum%2!=0) return false;
            int[] dp=new int[sum/2];
            return doDp(sum/2,0,0,nums,dp);
            
        }
        public boolean doDp(int max,int cur, int index,int[] nums, int[] dp){
            if(cur>max || index>=nums.length){
                return false;
            }else if(cur==max){
                return true;
            }
            if(dp[cur]==1){
                return true;
            }else if(dp[cur]==-1){
                return false;
            }
            boolean res = doDp(max, cur+nums[index],index+1,nums,dp) || doDp(max, cur,index+1,nums,dp);
            dp[cur]=res?1:-1;
            return res;
        }
    }
    

  • 0

    @Mino-De

    Hi Mino,

    thanks for sharing your modification to the algorithm!

    I thought we should store not only the index of the array we are currently computing the solution for, but also the current sum we have computed up to this index (that indicates the elements we have selected before the current one for the partition).

    In my opinion it was necessary because at index i, we could have different solutions depending on which elements we have selected previously for the partition.

    Anyway if your solution is storing just the index in a linear array and it got accepted, it seems to be a good space improvement, I will look more into it,

    Best!


  • 0
    L

    Why don't use boolean type for the DP array? Since the value only has two possibilities.


  • 0

    @lfzh123 said in Java Dynamic Programming Solution (21ms, with explanation):

    Why don't use boolean type for the DP array? Since the value only has two possibilities.

    Hi lfzh123!

    Actually I had to use a different type for the DP array, because it should have at least 3 values in my opinion;

    the problem of using a boolean array, is that the array is initialized at false by default, so when you encounter a false value in the array, you don't know if that false is due to the default initialization or because you have already computed that subproblem.

    This is why I used an integer array, but actually you can use a smaller type, as soon as you can differentiate the default value by the two computed values true or false (1 or 2 in my case); maybe you can use 'short' type to save some more space,

    Best


  • 0
    L

    @fabrizio3 Yes, thanks for pointing out. I realized it by running an example. :)


  • 1
    L

    I think we can use array of hashtable to save space


  • 0
    A

    I don't think this one qualifies for Dynamic programming. The sub problems are unique. My solution was without DP , and still it beat 88% java submissions. Someone correct me if I'm wrong.


  • 0
    A
    This post is deleted!

  • 0
    M

    @Avelin I feel that this is still Dynamic Progamming. isPartitionable is the sub problem.


  • 0

    @Avelin

    I agree with Mino, we divide the problem in subproblems, and store the partial results, it is dynamic programming


  • 0
    L

    Hi , thank you for sharing. What would happen if we select different elements but end up have the same index and current sum? Will it cause any problem?


  • 0
    F

    @Mino-De Hi Mino, your solution is great in both time and space performance. I got two problems, what is the time complexity of your solution? Secondly, when you get a first subset which has the sum of S, and you cannot find another subset which has the sum of Target - S, you record dp[sum] = -1. However, during the backtrack process, you may find another subset which has the sum of S, how can you guarantee there will not be another subset of sum of Target - S? I guess that's why we need to use two-dimensional array to store both the sum and indices.


Log in to reply
 

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