## 4 Sum

Given an array

*S*of*n*integers, are there elements*a*,*b*,*c*, and*d*in*S*such that*a*+*b*+*c*+*d*= target? Find all unique quadruplets in the array which gives the sum of target.**Note:**

- Elements in a quadruplet (
*a*,*b*,*c*,*d*) must be in non-descending order. (ie,*a*≤*b*≤*c*≤*d*) - The solution set must not contain duplicate quadruplets.

For example, given array S = {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)

### (Updated May 2014)

### Analysis:

This problem is slight different from "3 sum" but similar to "2 sum".The key idea is to think this problem as a "2 sum problem". But we have four values to deal with, how to solve it as a 2 sum way? Yes, we can firstly compute all the pair sums, then use these sums as the input of the 2 sum problem. Here pair sum means we select every 2 distinct elements and compute their sum, note that, we need to store the key-value carefully.

So, after we compute the sums, the indices

**i,j**and sum

**s**need to store into a map. In C++, it is a little complex because we must use

**multimap**to handle the

**one key multiple values**case.

Then use the "2sum" way, to find the results. Note that,

(1) In the two pairs, there must be no same index. e.g. mp[2] = <1,3> mp[3]=<2,3> , this is invalid.

(2) In the two pairs, we need to store it into a vector for output, the vector must be sorted as required. Because we have only 4 elements in the output vector, sort() takes constant time complexity.

(3) There must be no duplicates of output vectors. e.g.Input: [0, 1 2, 4], target = 7, mp[2] =<1,3>, mp[5]=<2,4>, mp[1]<1,2>, mp[6]=<3,4> (here <i,j> are indices), so the [1,3,2,4] and [1,2,3,4] are all valid, but actually they are the same. Here I use a set<vector<int> > to store and result vectors, finally change it to the vector <vector<int> >.

### Code(C++):

class Solution { public: vector<vector<int> > fourSum(vector<int> &num, int target) { vector<int> res_m(4); vector< vector<int> > res; multimap<int, pair<int,int> > mp; multimap<int, pair<int,int> >::iterator mit,mit2; set<vector<int> > mset; if (num.size()<4){ return res; } //Get all pair sums (every two-elements sums) for (int i=0;i<num.size()-1;i++){ for (int j=i+1;j<num.size();j++){ mp.insert(make_pair((num[i]+num[j]),make_pair(i,j))); } } //Use a multi map to find the results for (mit=mp.begin();mit!=mp.end();mit++){ if (mp.find(target- (*mit).first)!=mp.end()){ // if the target-current value exists in the map //handling the same key multi-value case pair <multimap<int,pair<int,int> >::iterator, multimap<int,pair<int,int> >::iterator> ret; ret = mp.equal_range(target- mit->first); //for all the values in the same key for (mit2=ret.first;mit2!=ret.second;++mit2){ //check if duplicates exist in the two pairs if (mit->second.first != mit2->second.first && mit->second.first != mit2->second.second && mit->second.second != mit2->second.first && mit->second.second != mit2->second.second){ res_m[0]=(num[mit->second.first]); res_m[1]=(num[mit->second.second]); res_m[2]=(num[mit2->second.first]); res_m[3]=(num[mit2->second.second]); sort(res_m.begin(),res_m.end()); mset.insert(res_m); // handles the duplicates } } } } //get result for (set<vector<int> >::iterator it=mset.begin();it!=mset.end();++it){ res.push_back(*it); } return res; } };

Cannot pass oj.... it4 not declared. Line 6 and 8 conflict. After correcting the compile errors. Still time limit exceed.

ReplyDeleteI am sorry about the wrong editing.

DeleteThe post has been updated and the code above have been tested on OJ.

Thank you very much for pointing out my mistake.

Hi, time limit exceeded for leetcode oj ......

ReplyDeleteWhat is the Time Complexity of this problem ?

ReplyDelete