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.