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

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

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