leetcode Question 3: 4 sum

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;
    }
};