# Four Sum Problem

## Description

LeetCode Problem 18. Given an array of integers **nums** and an integer **target**, return all unique quadruplets in the array (a, b, c, d),
which gives the sum of **target** (a + b + c + d = target).

Example:

1
2

Input: nums = [1, 0, -1, 0, -2, 2], target = 0
Output: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

## Solution

This problem is similar to the `two sum problem`

.

#### Brute Force Approach

A simple solution is to use the `brute force`

approach.

We loop through the array four times to get four different elements (*a*, *b*, *c*, *d*).
Then we check whether (*a* + *b* + *c* + *d* = *target*) is true or not.

If it is true, we add the quadruplets (*a*, *b*, *c*, *d*) to a set to ensure the final solutions do not contain duplicates; otherwise, we keep on searching.

The time complexity of this approach is O(n^{4}),
and the space complexity is O(n).

#### Two Pointer Approach

If the array is sorted, we can use the `two pointer`

approach to reduce the time and space complexity
(similar to the `three sum problem`

).

We first sort the array in ascending order, the time complexity of this step is O(nlogn).

In the `three sum problem`

, we iterate through the elements in the array and use the `two pointer`

approach to search the other two elements. In the `four sum problem`

, we can do something similar. We iterate through the array twice to get two elements. Then we use the `two pointer`

approach to search for the other two numbers.

For each two elements *nums[i]* and *nums[j]* (*nums[i]* <= *nums[j]*) in the array, we set two pointers pointing to the elements larger than *nums[j]*: the left pointer *l* points to
the smallest element on the right of *nums[j]*, and the right pointer *r* points to the largest element on the right of *nums[j]*.

We add the four numbers together (*nums[i]* + *nums[j]* + *nums[l]* + *nums[r]*) and compare it with *target*.

If the sum is greater than 0, that means *nums[r]* is too big for the triplet (and *nums[l]* is already the smallest possible one), so
we move the right pointer one step to the left (*r*-1) to try a smaller number.

If the sum is smaller than 0, that means *nums[l]* is too small for the triplet (and *nums[r]* is already the biggest possible one), so
we move the left pointer one step to the right (*l*+1) to try a bigger number.

If the sum is 0, we find one solution and insert it into a set (to make sure the final solutions do not contain duplicates). Then we move the
left pointer one step to the right (*l*+1), and the right pointer one step to the left (*r*-1). We move the left pointer one step to the right is
because if we only move the right pointer and keep the left pointer pointing to the current number,
the new *nums[r]* will be smaller or equal to the old *nums[r]*. If it is smaller, the sum of these three numbers will be less than 0.
If it is equal, then this solution will be the same as the original one. Same reason applies to why we move the right pointer one step to the left.

The time complexity can be reduced to O(n^{3}), while the
space complexity is still O(n).

## Sample C++ Code

This is a C++ implementation of the two pointer approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
set<vector<int>> s;
int l, r, sum;
int len = nums.size();
for (int i = 0; i < len - 3; i ++) {
for (int j = i + 1; j < len - 2; j ++) {
l = j + 1, r = len - 1;
while (l < r) {
sum = nums[i] + nums[j] + nums[l] + nums[r];
if (sum == target) {
s.insert({nums[i], nums[j], nums[l], nums[r]});
l ++;
r --;
} else if (sum > target) {
r --;
} else {
l ++;
}
}
}
}
for (auto x : s) {
ans.push_back(x);
}
return ans;
}
int main() {
vector<int> nums={1,0,-1,0,-2,2};
int target = 0;
vector<vector<int>> ans;
ans = fourSum(nums, target);
for (int i = 0; i < ans.size(); i ++) {
for (int j = 0; j < ans[i].size(); j ++) {
cout << ans[i][j] << " ";
}
cout << endl;
}
}