## 4 Sum Problem | Leetcode #18

This video explains a very important programming interview problem which is the 4 sum problem.This problem can be solved using multiple techniques and algorithms.I have explained all the approaches using simple examples.I have explained 3 techniques.The first one is just by using simple set which is the brute force approach.The second technique is by using set with 2 pointer technique. This is the best approach in terms of time complexity. The third approach is by using hashmap.This solution iis better than the naive approach.

## CODE

```//Simple SET
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
set<vector<int>> ans;
int n=nums.size();
sort(nums.begin(),nums.end());
int sum;

for(int i=0;i<n-3;++i) {
//if(i>0 and nums[i]==nums[i-1])  continue;   //Skip same values for index i to avoid duplicates
for(int j=i+1;j<n-2;++j) {
//if(j>i+1 and nums[j]==nums[j-1])    continue;   //Skip same values for index j to avoid duplicates
for(int k=j+1;k<n-1;++k) {
//if(k>j+1 and nums[k]==nums[k-1])    continue;   //Skip same values for index k to avoid duplicates
for(int l=k+1;l<n;++l) {
//if(l>k+1 and nums[l]==nums[l-1])    continue;   //Skip same values for index l to avoid duplicates
sum=nums[i]+nums[j]+nums[k]+nums[l];
if(sum>target)
break;
else if(sum==target) {
vector<int> t;
t.push_back(nums[i]);
t.push_back(nums[j]);
t.push_back(nums[k]);
t.push_back(nums[l]);
ans.insert(t);
}
}
}
}
}
vector<vector<int>> res;
for(auto it: ans)
res.push_back(it);
return res;
}
};

/*
//2-pointers + SET
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
set<vector<int>> ans;
int n=nums.size();
sort(nums.begin(),nums.end());
int sum;

for(int i=0;i<n-3;++i) {
if(i>0 and nums[i]==nums[i-1])  continue;   //Skip same values for index i to avoid duplicates
for(int j=i+1;j<n-2;++j) {
if(j>i+1 and nums[j]==nums[j-1])  continue;   //Skip same values for index j to avoid duplicates
int left=j+1,right=n-1;

while(left<right)   {   //2 pointer technique
sum=nums[i]+nums[j]+nums[left]+nums[right];
if(sum>target)
right-=1;
else if(sum==target) {
vector<int> t;
t.push_back(nums[i]);
t.push_back(nums[j]);
t.push_back(nums[left]);
t.push_back(nums[right]);
ans.insert(t);
left+=1;
}
else
left+=1;
}
}
}
vector<vector<int>> res;
for(auto it: ans)
res.push_back(it);
return res;
}
};

//HashMap
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ans;
int n = nums.size();
if(n<4)
return ans;

sort(nums.begin(),nums.end());
unordered_map<int,vector<pair<int,int>>> m;    //key->SUM...Value->(i,j) pair of index where i<j
//Store all sum pairs in map
for(int i=0;i<n-1;++i)
for(int j=i+1;j<n;++j)
m[nums[i]+nums[j]].push_back(make_pair(i,j));

for(int i=0;i<n-1;++i) {
if(i>0 and nums[i]==nums[i-1])  continue;
for(int j=i+1;j<n;++j) {
if(j>i+1 and nums[j]==nums[j-1])  continue;
int sum = target-nums[i]-nums[j];
if(m.find(sum)!=m.end()) {
for(auto it: m[sum])    {
int k=it.first;
int l=it.second;
if(k>j) {   //Maintain the increasing order of index (i,j,k,l).....i<j<k<l
//Skip invalid cases
if(!ans.empty() and ans.back()[0]==nums[i] and ans.back()[1]==nums[j] and ans.back()[2]==nums[k] and ans.back()[3]==nums[l])
continue;
vector<int> temp = {nums[i],nums[j],nums[k],nums[l]};
ans.push_back(temp);
}
}
}
}
}
return ans;
}
};
*/```

### One comment on “4 Sum Problem | Leetcode #18”

• Tech Dose January 20, 2022

Nice solution.