# Generic nSum Java Solution beats 98%

• ``````public class Solution {

// assume input array is sorted (can contain duplicates!)
public List<List<Integer>> nSum(int[] nums, int startIdx, int n, int target) {
ArrayList<List<Integer>> l = new ArrayList<List<Integer>>();

if(n <= 0 || startIdx >= nums.length || startIdx+n > nums.length)
return l;

// Note: this is important, early prune the cases where the sum of first n > target
int sum = 0;
for(int i=0; i<n; i++)
sum += nums[startIdx+i];
if (sum>target)
return l;

// Note: this is important, early prune the cases where the sum of last n < target
sum = 0;
for(int i=nums.length-1; i>=nums.length-n; i--)
sum += nums[i];
if (sum<target)
return l;

if(n==1) {
for(int i=startIdx; i<nums.length; i++) {
if(nums[i]==target) {
ArrayList<Integer> subL = new ArrayList<Integer>();
break;
}
}
} else {
int startVal = nums[startIdx];
int startCount = 1;
for(int i=startIdx+1; i<nums.length; i++) {
if(nums[i]==startVal)
startCount++;
else
break;
}
for(int i=0; i<=startCount; i++) {
List<List<Integer>> ls = nSum(nums,startIdx+startCount,n-i,target-i*startVal);
for(List<Integer> postLs : ls) { // merge the lists
ArrayList<Integer> prefixLs = new ArrayList<Integer>();
for(int j=1; j<=i; j++) // add duplicates startVals first
}
}
// Note: this is tricky, this handles the case the current target can consists of all duplicates values!
if(startCount>=n && target-n*startVal==0) {
System.out.println("Triggered " + startVal);
ArrayList<Integer> prefixLs = new ArrayList<Integer>();
for(int j=1; j<=n; j++)
}
}
return l;
}

public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
return nSum(nums, 0, 4, target);
}
}``````

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