In the 4Sum problem, we have given an integer x and an array a[ ] of size n. Find all the unique set of 4 elements in array such that sum of those 4 elements is equal to the given integer x.
Table of Contents
Example
Input
a[ ] = {1, 0, -1, 0, -2, 2}
x = 0
Output
1, 0, -1, 0
1, -1, -2, 2
0, 0, -2, 2
Input
a[ ] = {1, 2, 4, 3, -3, 0, -2}
x = 7
Output
1, 2, 4, 0
2, 4, 3, -2
Naive Method
Algorithm for 4Sum
- Initialize an array a[ ] of size n and an integer x.
- Traverse four-loop with the first loop starting from 0 to n-4 and rest three inner loops starting from the value of its outer loop + 1 till n-3, n-2 and n-1 respectively.
- Check if the sum of elements at all four indexes is equal to the given integer, print all four elements.
Time Complexity: O(n4) because we are check for four values and for each value we use one loop for find its all ways of selection.
Auxiliary Space: O(1) because we don’t use any auxiliary space in the implementation part.
C++ Program to find 4Sum
#include <bits/stdc++.h>
using namespace std;
void fourSum(int a[], int n, int x){
for(int i = 0; i < n-3; i++){
for(int j = i+1; j < n-2; j++){
for(int k = j+1; k < n-1; k++){
for(int l = k+1; l < n; l++){
if(a[i] + a[j] + a[k] + a[l] == x){
cout<<a[i]<<", "<<a[j]<<", "<<a[k]<<", "<<a[l]<<endl;
}
}
}
}
}
}
int main(){
int a[] = {1, 0, -1, 0, -2, 2};
int n = sizeof(a)/sizeof(a[0]);
int x = 0;
fourSum(a, n, x);
return 0;
}1, 0, -1, 0 1, -1, -2, 2 0, 0, -2, 2
Java Program to find 4Sum
class FourElementsSum{
void fourSum(int a[], int n, int x){
for(int i = 0; i < n-3; i++){
for(int j = i+1; j < n-2; j++){
for(int k = j+1; k < n-1; k++){
for(int l = k+1; l < n; l++){
if(a[i] + a[j] + a[k] + a[l] == x){
System.out.print(a[i]+", "+a[j]+", "+a[k]+", "+a[l]);
System.out.println();
}
}
}
}
}
}
public static void main(String[] args){
FourElementsSum f = new FourElementsSum();
int a[] = {1, 0, -1, 0, -2, 2};
int n = a.length;
int x = 0;
f.fourSum(a, n, x);
}
}1, 0, -1, 0 1, -1, -2, 2 0, 0, -2, 2
Using Sorting Method
Algorithm
- Initialize an array a[ ] of size n and an integer x.
- Sort the array using quicksort.
- Set the first element by traversing from 0 to n-4 and second element by traversing from Outer loop+1 to n-3.
- Set elements 3 and 4 as j+1 and element 4 as n-1.
- Traverse while the third element is less than fourth.
- Check if sum of these four elements is equal to a given integer, print the four elements, and increment the third element and decrement the fourth element.
- Else if the sum of these four elements is less than given integer, increment the third element.
- Else decrement the fourth element.
Time Complexity: O(n3) where n denotes the number of elements present in the input array.
Auxiliary Space: O(1) because here we don’t use any auxiliary space.
C++ Program to find 4Sum
#include <bits/stdc++.h>
using namespace std;
int compare(const void *a, const void * b){
return( *(int *)a - *(int *)b );
}
void fourSum(int a[], int n, int x){
int l, r;
qsort(a, n, sizeof(a[0]), compare);
for(int i = 0; i < n-3; i++){
for(int j = i+1; j < n-2; j++){
l = j+1;
r = n-1;
while(l < r){
if(a[i] + a[j] + a[l] + a[r] == x){
cout<<a[i]<<", "<<a[j]<<", "<<a[l]<<", "<<a[r]<<endl;
l++;
r--;
}
else if(a[i] + a[j] + a[l] + a[r] < x){
l++;
}
else{
r--;
}
}
}
}
}
int main(){
int a[] = {1, 0, -1, 0, -2, 2};
int n = sizeof(a)/sizeof(a[0]);
int x = 0;
fourSum(a, n, x);
return 0;
}-2, -1, 1, 2 -2, 0, 0, 2 -1, 0, 0, 1
Java Program to find 4Sum
import java.util.Arrays;
class FourElementsSum{
void fourSum(int a[], int n, int x){
int l, r;
Arrays.sort(a);
for(int i = 0; i < n-3; i++){
for(int j = i+1; j < n-2; j++){
l = j+1;
r = n-1;
while(l < r){
if(a[i] + a[j] + a[l] + a[r] == x){
System.out.println(a[i]+", "+a[j]+", "+a[l]+", "+a[r]);
l++;
r--;
}
else if(a[i] + a[j] + a[l] + a[r] < x)
l++;
else{
r--;
}
}
}
}
}
public static void main(String[] args){
FourElementsSum f = new FourElementsSum();
int a[] = {1, 0, -1, 0, -2, 2};
int n = a.length;
int x = 0;
f.fourSum(a, n, x);
}
}-2, -1, 1, 2 -2, 0, 0, 2 -1, 0, 0, 1
More Efficient Method
Algorithm
- Initialize a vector a[ ] of size n and an integer x.
- Create a 2D vector ans to store the result and an unordered map.
- Traverse through the vector and store the sum of all combinations in map.
- Search the target-sum in map.
- Create a vector of pair type of int, int and update it as map[target-sum].
- Traverse pair vector and initialise a new vector in it..
- Store the four chosen elements in this new vector.
- Sort the new vector.
- Check if sum of these four elements is equal and elements are not common either, push the elements in 2D vector ans.
- Print the 2D vector for the result.
Time Complexity: O(n2) where n denotes the number of elements in the given vector a.
Auxiliary Space: O(n2) because here we use n2 auxiliary space in vectors and hashmaps.
C++ Program to find 4Sum
#include <bits/stdc++.h>
using namespace std;
class FourElementsSum{
public:
bool notCommon(pair<int,int> p1,pair<int,int> p2){
if(p1.first!=p1.second && p2.first!=p1.second && p2.first!=p2.second && p1.first!=p2.second && p1.first!=p2.first && p1.second!=p2.second)
return true;
return false;
}
void fourSum(vector<int>& nums, int target){
vector<vector<int>> ans;
if(nums.size()<4)
cout<<"Size is less than 4";
unordered_map<int,vector<pair<int,int>> > m;
for(int i=0; i<nums.size()-1; i++){
for(int j=i+1; j<nums.size(); j++){
m[nums[i]+nums[j]].push_back(make_pair(i,j));
}
}
for(int i=0; i<nums.size(); i++){
for(int j=i+1; j<nums.size(); j++){
int sum=nums[i]+nums[j];
if(m.find(target-sum)!=m.end()){
vector<pair<int,int>> p=m[target-sum];
for(int k=0;k<p.size();k++){
vector<int> v;
v.push_back(nums[i]);
v.push_back(nums[j]);
v.push_back(nums[m[target-sum][k].first]);
v.push_back(nums[m[target-sum][k].second]);
sort(v.begin(),v.end());
if(find(ans.begin(),ans.end(),v)==ans.end()&& notCommon(make_pair(i,j),m[target-sum][k]) )
ans.push_back(v);
}
}
}
}
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < ans[i].size(); j++){
cout << ans[i][j] << " ";
}
cout << endl;
}
}
};
int main(){
FourElementsSum f;
vector<int> a = {1, 0, -1, 0, -2, 2};
int x = 0;
f.fourSum(a, x);
return 0;
}-1 0 0 1 -2 -1 1 2 -2 0 0 2