Solution to LeetCode 4Sum problem.
Same idea as with 3SUM, except we have one more index to keep track of, and we have more trickery with indices.
public ArrayList<ArrayList<Integer>> fourSum(int[] A, int target) {
Arrays.sort(A);
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
int N = A.length;
for(int i = 0; i < N-3; i++){
for(int j = i+1; j < N-2; j++){
int k = j+1;
int l = N-1;
while(k < l){
int sum = A[i]+A[j]+A[k]+A[l];
if(sum-target < 0) k++;
if(sum-target > 0) l--;
else if(sum-target == 0){
res.add(new ArrayList<Integer>(Arrays.asList(new Integer[]{A[i],A[j],A[k],A[l]})));
do{ k++; } while(k < l && A[k] == A[k-1]);
do{ l--; } while(k < l && A[l] == A[l+1]);
}
}
while(j < N-1 && A[j] == A[j+1]) j++; // Note the other increment at loop head
}
while(i < N-2 && A[i] == A[i+1]) i++; // Note the other increment at loop head
}
return res;
}