# 4Sum Leetcode Solution

#### ByBrokenprogrammers

Dec 5, 2022

In this post, you will know how to solve the 4Sum Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.

## 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`

### 4Sum Leetcode Solutions in 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
```

### 4Sum Leetcode Solutions in 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 Solutions 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.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;
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 BrokenProgrammers. This tutorial is only for Educational and Learning purposes.