Java DFS with early termination check (50ms very fast in DFS)


  • 0
    X

    Code is as following, hoping somebody can make improvement

    int count;
    int[] sum;
    //Memorize how many 0s are left
    int[] count0;
    int len;
    public int findTargetSumWays(int[] nums, int S) {
        count=0;
        len = nums.length;
        if(len==0){
            return count;
        }
        //Sort to make dfs run faster
        Arrays.sort(nums);
        int l=0;
        int r=len-1;
        while(l<r){
            nums[l]^=nums[r];
            nums[r]^=nums[l];
            nums[l]^=nums[r];
            l++;
            r--;
        }
        sum = new int[len];
        sum[len-1]=nums[len-1];
        count0 = new int[len];
        if(nums[len-1]==0){
            count0[len-1]=1;
        }
        for(int i=len-2;i>=0;i--){
            sum[i]=sum[i+1]+nums[i];
            if(nums[i]==0){
                count0[i]=count0[i+1]+1;
            }else{
                count0[i]=count0[i+1];
            }
        }
        if(sum[0]<S||sum[0]<-S||(sum[0]+S)%2!=0){
            return count;
        }
        dfs(nums,0,S);
        return count;
    }
    public void dfs(int[] nums,int index,int target){
        if(index==len){
            if(target==0){
                count++;
            }
            return;
        }
     //early termination check 
        if(sum[index]<target||sum[index]<-target||(sum[index]+target)%2!=0){
            return;
        }
    //If the sum of left element is equal to Math.abs(target), add 2^(numbers of 0 in left element)
        if(sum[index]==target||sum[index]==-target){
            count+=1<<count0[index];
            return;
        }        
        dfs(nums,index+1,target-nums[index]);
        dfs(nums,index+1,target+nums[index]);
        return;
    }

Log in to reply
 

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