# LeetCode 18. 4Sum: CPP Solution

## Problem Statement

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

``````Function Signature (C++):
vector<vector<int>> fourSum(vector<int>& nums, int target)

Inputs:
nums = [1, 0, -1, 0, -2, 2]
target = 0

Outputs:
[
[-1,  0, 0, 1],
[-2, -1, 1, 2],
[-2,  0, 0, 2]
]
``````

## TL;DR Code Solution

``````vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());

vector<vector<int>> result;

int size = (int)nums.size();
for (int i = 0; i < size - 3; i++) {
int first = nums[i];
for (int j = i + 1; j < size - 2; j++) {
int second = nums[j];
int left = j + 1;
int right = size - 1;
while (left < right) {
int numLeft = nums[left];
int numRight = nums[right];

int sum = first + second + nums[left] + nums[right];
if (sum == target) {
vector<int> current = {first, second, nums[left], nums[right]};
result.push_back(current);

while (left < right && nums[left] == numLeft)
left++;
while (left < right && nums[right] == numRight)
right--;
}
else if (sum < target) {
left++;
}
else {
right--;
}
}
while (j + 1 < size  - 2 && nums[j+1] == nums[j])
j++;
}
while (i + 1 < size  - 3 && nums[i+1] == nums[i])
i++;
}

return result;
}
``````