# The evolution of my brute force thinking, hope can help those who can't really come up with a iterative dp[nums.length][sum/2] solution

• Just like a mediocre programmer, at my first sight of this question, I know there are some dirty brute force solutions that can give you the right answer, slowly and unacceptably. So I came up with this one:

public boolean canPartition(int[] nums) {
if(nums.length<=1)return false;
int sum = 0;
for(int e:nums)sum += e;
if((sum&1)!=0)return false;//you can't divide a odd number into two equal pieces
int target = sum/2;
//now the problem becomes can we use any combination of numbers in the nums[] to achieve the target
return weCan(0,target,nums);//just assume we can bros
}
boolean weCan(int i,int res,int[] nums){
if(flag)return true;
if(i==nums.length||res<0)return false;
if(res==0){return true;}
return weCan(i+1,res-nums[i],nums)||weCan(i+1,res,nums);//At each step all the way to the end of the array, you have only two choices: pick current number/ ignore it
}

It is obvious that the complexity 2^n which is too high to be acceptable. So as always, by adding a memory cache, we can remember the previous results a each step so that a redundant calculation can be avoided.

public boolean canPartition(int[] nums) {
if(nums.length<=1)return false;
int sum = 0;
for(int e:nums)sum += e;
if((sum&1)!=0)return false;
int target = sum/2;
HashMap<String,Boolean> map = new HashMap<>();//add a cache to remember the calculated reuslts
int[][]dp = new int[nums.length][target+1];
//can we achieve target?
return weCan(0,target,nums, map);
}
boolean weCan(int i,int res,int[] nums, HashMap<String,Boolean> map){
StringBuilder sb = new StringBuilder();
sb.append(i+"/"+res);
String key = sb.toString();//using the current index number and residue as a key
if(map.containsKey(key))return map.get(key);
if(i==nums.length||res<0)return false;
if(res==0){;return true;}
boolean result =  weCan(i+1,res-nums[i],nums,map)||weCan(i+1,res,nums,map);
map.put(sb.toString(),result);
return result;
}

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