## Algorithm

Problem Name: 18. 4Sum

Given an array `nums` of `n` integers, return an array of all the unique quadruplets `[nums[a], nums[b], nums[c], nums[d]]` such that:

• `0 <= a, b, c, d < n`
• `a`, `b`, `c`, and `d` are distinct.
• `nums[a] + nums[b] + nums[c] + nums[d] == target`

You may return the answer in any order.

Example 1:

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

Example 2:

```Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
```

Constraints:

• `1 <= nums.length <= 200`
• `-109 <= nums[i] <= 109`
• `-109 <= target <= 109`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector < vector<int>>res;
vector<int>path;
DFS(res, nums, 0, target, 0, 0, path);
return res;
}

void DFS(vector < vector<int>>& res, vector<int>& nums, int pos, int target, int count, int sum, vector<int>& path){
if(count == 4){
if(sum == target) res.push_back(path);
return;
}
for(int i = pos; i < nums.size(); i++){
if(i != pos && nums[i] == nums[i - 1]) continue;
if(sum + nums[i] + (3 - count) * nums[nums.size() - 1]  <  target) continue;
if(sum + (4 - count>* nums[i] > target) break;
path.push_back(nums[i]);
DFS(res, nums, i + 1, target, count + 1, sum + nums[i], path);
path.pop_back();
}
}
};

``````
Copy The Code &

Input

cmd
nums = [1,0,-1,0,-2,2], target = 0

Output

cmd
[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List();
if (start == nums.length) {
return result;
}
long averageValue = target / k;
if  (nums[start] > averageValue || averageValue > nums[nums.length - 1]) {
return result;
}
if (k == 2) {
return twoSum(nums, target, start);
}
for (int i = start; i  <  nums.length; ++i) {
if (i == start || nums[i - 1] != nums[i]) {
for (List subset : kSum(nums, target - nums[i], i + 1, k - 1)) {
}
}
}
return result;
}

public List < List();
int low = start;
int high = nums.length - 1;
while (low  <  high) {
int currSum = nums[low] + nums[high];
if (currSum < target || (low > start && nums[low] == nums[low - 1])) {
++low;
} else if (currSum > target || (high  <  nums.length - 1 && nums[high] == nums[high + 1])) {
--high;
} else {
}
}
return result;
}
}

``````
Copy The Code &

Input

cmd
nums = [2,2,2,2,2], target = 8

Output

cmd
[[2,2,2,2]]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const fourSum = function (nums, target) {
nums.sort((a, b) => a - b)
const results = []
kSum(nums, target, 4, 0, [], results)
return results
}

function kSum(nums, target, k, i, acc, results) {
if (nums[i] * k > target || nums[nums.length - 1] * k < target) return
if (k > 2) {
for (let j = i; j  < = nums.length - k; j++) {
if (j == i || nums[j] > nums[j - 1])
kSum(nums, target - nums[j], k - 1, j + 1, [...acc, nums[j]], results)
}
} else {
twoSum(nums, target, i, acc, results)
}
}

function twoSum(nums, target, i, acc, results) {
let lo = i
let hi = nums.length - 1
while (lo < hi) {
const sum = nums[lo] + nums[hi]
if (sum == target) {
results.push([...acc, nums[lo], nums[hi]])
while (nums[lo] == nums[lo + 1]) lo++
while (nums[hi] == nums[hi - 1]) hi--
lo++
hi--
} else if (sum < target) {
lo++
} else {
hi--
}
}
}
``````
Copy The Code &

Input

cmd
nums = [2,2,2,2,2], target = 8

Output

cmd
[[2,2,2,2]]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def fourSum(self, nums, target):
res, res_set = [], set()
nums.sort()
for i in range(len(nums) - 1):
if i > 0 and nums[i] == nums[i - 1]: continue
for j in range(i + 1, len(nums)):
l, r = j + 1, len(nums) - 1
while l < r:
sm = nums[i] + nums[j] + nums[l] + nums[r]
if sm < target: l += 1
elif sm > target: r -= 1
elif (nums[i], nums[j], nums[l], nums[r]) not in res_set:
res.append([nums[i], nums[j], nums[l], nums[r]]); res_set.add((nums[i], nums[j], nums[l], nums[r]))
else: l, r = l + 1, r - 1
return res
``````
Copy The Code &

Input

cmd
nums = [1,0,-1,0,-2,2], target = 0

Output

cmd
[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _018_4Sum
{
public IList < IList<int>> FourSum(int[] nums, int target)
{
var results = new List < IList<int>>();
if (nums.Length  <  4) { return results; }

Suffle(nums);
Quick3WaySort(nums, 0, nums.Length - 1);

var cache = new Dictionary < int, IList<int>>();
int temp, index1, index2;
for (index1 = 0; index1  <  nums.Length - 1; index1++)
{
for (index2 = index1 + 1; index2  <  nums.Length; index2++)
{
temp = nums[index1] + nums[index2];
if (!cache.ContainsKey(temp))
{
cache[temp] = new List < int>();
}
}
}

IList < int> list1, list2;
foreach (var pair in cache)
{
if (!cache.TryGetValue(target - pair.Key, out list2)) { continue; }
list1 = pair.Value;

for (index1 = 0; index1  <  list1.Count; index1 += 2)
{
for (index2 = 0; index2  <  list2.Count; index2 += 2)
{
if ((list1[index1 + 1] < list2[index2]) && (list1[index1] != list2[index2] && list1[index1] != list2[index2 + 1]))
{
results.Add(new List<int>() { nums[list1[index1]], nums[list1[index1 + 1]], nums[list2[index2]], nums[list2[index2 + 1]] });
while (index2 + 2  <  list2.Count && nums[list2[index2 + 2]] == nums[list2[index2]])
{
index2 += 2;
}
}
}

while (index1 + 2 < list1.Count && nums[list1[index1 + 3]] == nums[list1[index1 + 1]])
{
index1 += 2;
}
}
}

return results;
}

void Suffle(int[] nums)
{
var random = new Random();
int N = nums.Length;
int r, temp;
for (int i = 0; i  <  N; i++)
{
r = random.Next(i + 1);

temp = nums[r];
nums[r] = nums[i];
nums[i] = temp;
}
}

void Quick3WaySort(int[] nums, int lo, int hi)
{
if (lo >= hi) { return; }
var lt = lo;
var gt = hi;
var i = lo;
var v = nums[i];
int temp;

while (i  < = gt)
{
if (nums[i] > v)
{
temp = nums[i];
nums[i] = nums[gt];
nums[gt--] = temp;
}
else if (nums[i]  <  v)
{
temp = nums[i];
nums[i] = nums[lt];
nums[lt++] = temp;
}
else { i++; }
}
Quick3WaySort(nums, lo, lt - 1);
Quick3WaySort(nums, gt + 1, hi);
}
}
}

``````
Copy The Code &

Input

cmd
nums = [2,2,2,2,2], target = 8

Output

cmd
[[2,2,2,2]]