# 18. 4Sum

Given an array S of n integers, are there elements a,b,c, and d in S such that a+b+c+d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:The solution set must not contain duplicate quadruplets.

``````For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
[-1,  0, 0, 1],
[-2, -1, 1, 2],
[-2,  0, 0, 2]
]
``````

Thoughts:

1. Naive way: break down problems into 3Sum -> Two Sum; In general: for sum, use recursion to break down to (k-1)->(k-2) until reaching 2, which is solved using the algorithm for two Sum
2. Since we need ALL solutions, tricks for removing duplicates, as adopted in 3Sum is also adopted.
3. When k > 2, I prefer using two pointers as the time complexities is no longer dominant by sorting (O(nlogn)).
``````public class Solution {
public List<List<Integer>> fourSum(int[] num, int target) {
ArrayList<List<Integer>> ans = new ArrayList<>();
if(num.length<4)return ans;
Arrays.sort(num);
for(int i=0; i<num.length-3; i++){
if(num[i]+num[i+1]+num[i+2]+num[i+3]>target)break; //first candidate too large, search finished
if(num[i]+num[num.length-1]+num[num.length-2]+num[num.length-3]<target)continue; //first candidate too small
if(i>0&&num[i]==num[i-1])continue; //deduplicates
for(int j=i+1; j<num.length-2; j++){
if(num[i]+num[j]+num[j+1]+num[j+2]>target)break; //second candidate too large
if(num[i]+num[j]+num[num.length-1]+num[num.length-2]<target)continue; //second candidate too small
if(j>i+1&&num[j]==num[j-1])continue; //prevents duplicate results in ans list
int low=j+1, high=num.length-1;
while(low<high){
int sum=num[i]+num[j]+num[low]+num[high];
if(sum==target){
ans.add(Arrays.asList(num[i], num[j], num[low], num[high]));
while(low<high&&num[low]==num[low+1])low++; //skipping over duplicate on low
while(low<high&&num[high]==num[high-1])high--; //skipping over duplicate on high
low++;
high--;
}
//move window
else if(sum<target)low++;
else high--;
}
}
}
return ans;
}
``````

Special thanks: 洗刷刷 for the reference!