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


  • 0
    Z

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

Log in to reply
 

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