**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] ]

## 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 equal 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 )

## ASHISH BHARDWAJ

Nicee i think you should make a video on this on youtube….. very nuce thanks

## ajay

In the future, I shall think about it. Thanks for the suggestion.