Note:
The solution set must not contain duplicate quadruplets.
Example:
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
This problem is also called as 4 sums.
Now before we solve this problem, you need to know how to solve 3 sums and 2 sums problem.
4sums is a follow up question for 3sums which in-turn is a follow up for 2sums problem.
Hence I recommend you to solve 3sums and 2sums problem before you solve this problem.
Below are the steps to solve this problem.
Step 1: Sort the array in ascending order.
Step 2:
Now we need to find 4 elements such that:
arr[0] + arr[1] + arr[2] + arr[3] = 0
This can be written as
arr[0] + 3sum = key
Here arr[0] is -2 and key is 0.
Hence we need to find 3 numbers such that arr[0] + 3sum = 0. Means, the 3numbers should be equal to “2” so that the four sums is equall to 0.
Now the 3sum can be converted into 2 sum.
arr[1] + arr[2] + arr[3] = 2
i.e arr[1] + 2sums = 2
Here arr[1] is -1. Hence we need to find 2 numbers such that arr[1] + 2sum = 2.
Hence using 2sum solution, we need to find 2 numbers whose key is 3.
Therefore
Using the left and right pointers we find the 2 numbers.
Finally, we add all the numbers, and if it is equal to the original key, we save it in an array.
At the end we display the result.
Below is the solution in C++
#include<iostream>
#include<vector>
using namespace std;
vector<vector<int> > fourSums (vector<int> &arr, int key)
{
vector<vector<int> > final_result_set;
sort(arr.begin(), arr.end());
int len = arr.size();
for (int i = 0; i < arr.size() - 3; i++)
{
if (i != 0 && arr[i] == arr[i - 1])
{
continue;
}
for (int j = i + 1; j < arr.size() - 2; j++)
{
if (j != i + 1 && arr[j] == arr[j - 1])
{
continue;
}
int left_pointer = j + 1;
int right_pointer = arr.size() - 1;
while (left_pointer < right_pointer)
{
int sum = arr[i] + arr[j] + arr[left_pointer] + arr[right_pointer];
if (sum < key)
{
left_pointer++;
}
else if (sum > key)
{
right_pointer--;
}
else
{
vector<int> quadruplet ;
quadruplet.push_back(arr[i]);
quadruplet.push_back(arr[j]);
quadruplet.push_back(arr[left_pointer]);
quadruplet.push_back(arr[right_pointer]);
final_result_set.push_back(quadruplet);
left_pointer++;
right_pointer--;
while (left_pointer < right_pointer && arr[left_pointer] == arr[left_pointer - 1])
{
left_pointer++;
}
while (left_pointer < right_pointer && arr[right_pointer] == arr[right_pointer + 1])
{
right_pointer--;
}
}
}
}
}
return final_result_set;
}
int main() {
vector<int> arr;
int key = 0;
arr.push_back(1);
arr.push_back(0);
arr.push_back(-1);
arr.push_back(0);
arr.push_back(-2);
arr.push_back(2);
vector<vector<int> > final_set = fourSums(arr, key);
// If final_set is empty, then
if (final_set.size() == 0)
{
cout << "No possible combinations found";
return 0;
}
// print the output
for (int i = 0; i < final_set.size(); i++)
{
if (final_set[i].size() > 0)
{
cout << " ( ";
for (int j = 0; j < final_set[i].size(); j++)
cout << final_set[i][j] << " ";
cout << ")";
}
cout<<endl;
}
return 0;
}
Output:
( -2 -1 1 2 )
( -2 0 0 2 )
( -1 0 0 1 )