# 4Sum – Leetcode Solution

In this post, we are going to solve the 18. 4Sum problem of Leetcode. This problem 18. 4Sum is a Leetcode medium level problem. Let’s see code, 18. 4Sum.

Contents

## Problem

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`

Now, let’s see the code of 18. 4Sum – Leetcode Solution.

# 4Sum – Leetcode Solution

### 18. 4Sum – Solution in Java

```class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
int n = nums.length;
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if (i > 0 && nums[i - 1] == nums[i]) continue;
threeSum(nums, i + 1, n - 1, target - nums[i], result);
}
return result;
}

private void threeSum(int[] nums, int lo, int hi, int target, List<List<Integer>> result) {
int n = nums.length;
int subLen = hi - lo + 1;
for (int i = lo; i <= hi; ++i) {
if (i > lo && nums[i] == nums[i - 1]) continue;
int j = i + 1, k = hi;
int t = target - nums[i];
while (j < k) {
if (nums[j] + nums[k] < t) {
++j;
} else if (nums[j] + nums[k] > t) {
--k;
} else {
result.add(Arrays.asList(nums[lo - 1], nums[i], nums[j], nums[k]));
++j;
--k;
while (j < k && nums[j] == nums[j - 1]) j++;
while (j < k && nums[k] == nums[k + 1]) k--;
}
}
}
}
}```

### 18. 4Sum – Solution in C++

```class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> total;
int n = nums.size();
sort(nums.begin(),nums.end());
for(int i=0;i<n-3;i++)
{
if(i>0&&nums[i]==nums[i-1]) continue;
if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
for(int j=i+1;j<n-2;j++)
{
if(j>i+1&&nums[j]==nums[j-1]) continue;
if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
int left=j+1,right=n-1;
while(left<right){
int sum=nums[left]+nums[right]+nums[i]+nums[j];
if(sum<target) left++;
else if(sum>target) right--;
else{
total.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
do{left++;}while(nums[left]==nums[left-1]&&left<right);
do{right--;}while(nums[right]==nums[right+1]&&left<right);
}
}
}
}
}
};```

### 18. 4Sum– Solution in Python

```class Solution:
def fourSum(self, num, target):
two_sum = collections.defaultdict(list)
res = set()
for (n1, i1), (n2, i2) in itertools.combinations(enumerate(num), 2):
two_sum[i1+i2].append({n1, n2})
for t in list(two_sum.keys()):
if not two_sum[target-t]:
continue
for pair1 in two_sum[t]:
for pair2 in two_sum[target-t]:
if pair1.isdisjoint(pair2):
res.add(tuple(sorted(num[i] for i in pair1 | pair2)))
del two_sum[t]
return [list(r) for r in res]```

Note: This problem 18. 4Sum is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.