# 4 Sum Program Solution

We at gradjobopenings.com provide free job alerts of freshers job drives. In this website we list on campus job openings for freshers and off campus job openings for freshers and also work from home job openings. This is the best website to apply for off campus drive in India. Visit our website for government job alerts and private job alerts. We also list free interview notes and study materials, one of the best interview study website.comfortable to face the interviews:

Problem Statement:

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`
• Time: O(n^3)O(n3)
• Space: O(1)O(1)

### 4 Sum Program Solution In C++

``````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, int n, int 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 similar 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();
}
}
};
``````

### 4 Sum Program 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, int n, int 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 similar 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);
}
}
}
``````

### 4 Sum Program Solution 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:
sum = nums[l] + nums[r]
if sum == target:
ans.append(path + [nums[l], nums[r]])
l += 1
while nums[l] == nums[l - 1] and l < r:
l += 1
elif sum < 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
``````
error: Content is protected !!