# [LeetCode 18] 4Sum

### Question

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. (ie, abcd)
• 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)
```

### Stats

 Frequency 2 Diffficulty 3 Adjusted Difficulty 4 Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

This is exactly the same algorithm as 3Sum. The idea is for every value pair (a, b), find all (c, d) that makes the sum equals to the target.

Note that the final found result (a, b, c, d) is already in sorted order, no need to re-sort.

### Solution

The solution works in O(n3), which is a very common solution. Read this blog for a O(n2) solution. Read it ONLY if you are interested.

### My code

``````public class Solution {
public List<List<Integer>> fourSum(int[] num, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
if (num == null || num.length < 4) {
return ans;
}
Arrays.sort(num);
int len = num.length;
for (int i = 0; i < len - 3; i++) {
// make sure the first number is distinct
if (i != 0 && num[i - 1] == num[i]) {
continue;
}
for (int j = i + 1; j < len - 2; j++) {
// make sure the second number is distinct
if (j != i + 1 && num[j - 1] == num[j]) {
continue;
}
int balance = target - num[i] - num[j];
int left = j + 1;
int right = len - 1;
while (left < right) {
int sum = num[left] + num[right];
if (sum == balance) {
List<Integer> lis = new ArrayList<Integer>();
}
if (sum >= balance) {
// move right pointer left (to a unique value)
right--;
while (right >= 0 && num[right] == num[right + 1]) {
right--;
}
}
if (sum <= balance) {
// move left pointer right (to a unique value)
left++;
while (left < len && num[left] == num[left - 1]) {
left++;
}
}
}
}
}
return ans;
}
}
``````

We can also use HashMap to remove duplication. I personally would not recommend doing this, but it gives an interesting viwepoint. Check out this code.

``````public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
Arrays.sort(num);
HashSet<ArrayList<Integer>> hashSet = new HashSet<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < num.length; i++) {
for (int j = i + 1; j < num.length; j++) {
int k = j + 1;
int l = num.length - 1;
while (k < l) {
int sum = num[i] + num[j] + num[k] + num[l];
if (sum > target) l--;
else if (sum < target) k++;
else if (sum == target) {
ArrayList<Integer> temp =
new ArrayList<Integer>();