# 4Sum Leetcode Solution

In this post, we are going to solve the 4Sum Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Table of 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, lets see the leetcode solution of 4Sum Leetcode Solution.

### 4Sum Leetcode Solutionin Python

```class Solution:
def fourSum(self, nums: List[int], target: int):
ans = []

def nSum(l: int, r: int, target: int, n: int, path: List[int], ans: List[List[int]]) -> None:
if r - l + 1 < n or n < 2 or target < nums[l] * n or target > nums[r] * n:
return
if n == 2:
while l < r:
summ = nums[l] + nums[r]
if summ == target:
ans.append(path + [nums[l], nums[r]])
l += 1
while nums[l] == nums[l - 1] and l < r:
l += 1
elif summ < target:
l += 1
else:
r -= 1
return

for i in range(l, r + 1):
if i > l and nums[i] == nums[i - 1]:
continue

nSum(i + 1, r, target - nums[i], n - 1, path + [nums[i]], ans)

nums.sort()
nSum(0, len(nums) - 1, target, 4, [], ans)
return ans
```

### 4SumLeetcode Solutionin CPP

```class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ans;
vector<int> path;

sort(begin(nums), end(nums));
nSum(nums, 4, target, 0, nums.size() - 1, path, ans);
return ans;
}

private:
// In [l, r], find n numbers add up to the target
void nSum(const vector<int>& nums, long n, long target, int l, int r,
vector<int>& path, vector<vector<int>>& ans) {
if (r - l + 1 < n || target < nums[l] * n || target > nums[r] * n)
return;
if (n == 2) {
// Very simliar to the sub procedure in 15. 3Sum
while (l < r) {
const int sum = nums[l] + nums[r];
if (sum == target) {
path.push_back(nums[l]);
path.push_back(nums[r]);
ans.push_back(path);
path.pop_back();
path.pop_back();
++l;
--r;
while (l < r && nums[l] == nums[l - 1])
++l;
while (l < r && nums[r] == nums[r + 1])
--r;
} else if (sum < target) {
++l;
} else {
--r;
}
}
return;
}

for (int i = l; i <= r; ++i) {
if (i > l && nums[i] == nums[i - 1])
continue;
path.push_back(nums[i]);
nSum(nums, n - 1, target - nums[i], i + 1, r, path, ans);
path.pop_back();
}
}
};
```

### 4Sum Leetcode Solution in Java

```class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<>();

Arrays.sort(nums);
nSum(nums, 4, target, 0, nums.length - 1, new ArrayList<>(), ans);
return ans;
}

// In [l, r], find n numbers add up to the target
private void nSum(int[] nums, long n, long target, int l, int r, List<Integer> path,
List<List<Integer>> ans) {
if (r - l + 1 < n || target < nums[l] * n || target > nums[r] * n)
return;
if (n == 2) {
// Very simliar to the sub procedure in 15. 3Sum
while (l < r) {
final int sum = nums[l] + nums[r];
if (sum == target) {
path.add(nums[l]);
path.add(nums[r]);
ans.add(new ArrayList<>(path));
path.remove(path.size() - 1);
path.remove(path.size() - 1);
++l;
--r;
while (l < r && nums[l] == nums[l - 1])
++l;
while (l < r && nums[r] == nums[r + 1])
--r;
} else if (sum < target) {
++l;
} else {
--r;
}
}
return;
}

for (int i = l; i <= r; ++i) {
if (i > l && nums[i] == nums[i - 1])
continue;
path.add(nums[i]);
nSum(nums, n - 1, target - nums[i], i + 1, r, path, ans);
path.remove(path.size() - 1);
}
}
}
```

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

Sharing Is Caring