## Finding all unique quadruplets that sums to zero (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:

• Elements in a quadruplet $(a,b,c,d)$ must be in non-descending order. (i.e., $a \leq b \leq c \leq d$)
• The solution set must not contain duplicate quadruplets.

INPUT: $S$ = {1, 0, -1, 0, -2, 2}, and target = 0
OUTPUT: (-1, 0, 0, 1), (-2, -1, 1, 2) and (-2, 0, 0, 2)

Thoughts:
The same algorithm as in 3sum. $O(n^{3})$ algorithm.

Code (Java):

public class Solution {
public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
ArrayList<ArrayList<Integer>> sol = new ArrayList<ArrayList<Integer>>();
Arrays.sort(num);
for(int i = 0; i < num.length; ++i) {
for(int j = i + 1; j < num.length; ++j) {
int low = j + 1;
int high = num.length - 1;
while(low < high) {
int sum = num[i] + num[j] + num[low] + num[high];
if(sum > target)
high--;
else if(sum < target)
low++;
else {
low++;
high--;
}
}
}
}
return sol;
}
}

Code (C++):
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
vector<vector<int> > sol;
sort(num.begin(), num.end());
for(int i = 0; i < num.size(); ++i) {
for(int j = i + 1; j < num.size(); ++j) {
int low = j + 1;
int high = num.size() - 1;
while(low < high) {
int sum = num[i] + num[j] + num[low] + num[high];
if(sum > target)
high--;
else if(sum < target)
low++;
else {
low++;
high--;
}
}
}
}
return sol;
}
};

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b2dea9ca361b', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b2dea9ca364f',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b2dea9ca3651',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});