# Leetcode 18 Solution

https://leetcode.com/problems/4sum

## Thinking Process

Similar to the question 3sum, we fix the first two numbers, and then apply the sorted two sum algorithm.

## Time & Space Complexity

Assuming `N` is the size of the array

• Time complexity: `O(N^3)`
• Space complexity: `O(N)`

## Solution

``````class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());

for (int i = 0; i < nums.size(); i++)
{
if (i > 0 && nums[i] == nums[i - 1])
continue;

for (int j = i + 1; j < nums.size(); j++)
{
if (j > i + 1 && nums[j] == nums[j - 1])
continue;

int l = j + 1;
int r = nums.size() - 1;

while (l < r)
{
int s = nums[i] + nums[j] + nums[l] + nums[r];

if (s < target)
l++;
else if (s > target)
r--;
else
{
vector<int> a;
a.push_back(nums[i]);
a.push_back(nums[j]);
a.push_back(nums[l]);
a.push_back(nums[r]);

res.push_back(a);

do
{
l++;
} while (nums[l] == nums[l - 1] && l < nums.size());

do
{
r--;
} while (nums[r] == nums[r + 1] && r >= j + 1);
}
}
}
}

return res;
}
};
``````