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.length1) 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;
}
Java Dynamic Programming Solution (21ms, with explanation)


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

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!

@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


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

@MinoDe 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 twodimensional array to store both the sum and indices.