13ms java recursive with memorization solution


  • 0
    L
    public boolean canPartition(int[] nums) {
            int target=0;
            for(int n:nums) target +=n;
            if(target%2!=0) return false;
            target/=2;
            boolean[] sumchecks = new boolean[target+1];
            boolean[] selects = new boolean[nums.length];
            return canPartition(nums,selects,target,0,sumchecks);
        }
        boolean canPartition(int[] nums, boolean[] selects, int target,int sum,boolean[] sumchecks) {
            if(target==sum) {
                return true;
            }
            for(int i=0;i<nums.length;i++) {
                if(!selects[i]) {
                    selects[i]=true;
                    sum+=nums[i];
                    if(sum<=target&&!sumchecks[sum]) {
                        sumchecks[sum]=true;
                        if(canPartition(nums,selects,target,sum,sumchecks)) {
                            selects[i]=false;
                            return true;
                        }
                    }
                    selects[i]=false;
                    sum-=nums[i];
                }
            }
            return false;
        }
    
    

Log in to reply
 

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