LeetCode Problem : 4Sum

Problem

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)

Code

vector<pair<int,int> > two_sum(const vector<int> &A,int left,int right,int target)
{
    int clast = INT_MAX,dlast = INT_MAX;
    vector<pair<int,int> > result;
    while(left < right){
        if(A[left] == clast){
            ++left;
            continue;
        }
        if(A[right] == dlast){
            --right;
            continue;
        }
        int sum = A[left] + A[right];
        if(sum > target){
            dlast = A[right];
            --right;
        }
        else if(sum < target){
            clast = A[left];
            ++left;
        }
        else{
            result.push_back(make_pair(A[left] , A[right]));
            clast = A[left];
            dlast = A[right];
            ++left;--right;
        }
    }
    return result;
}
vector<vector<int> > fourSum(vector<int> &num, int target) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    vector<vector<int> > result;
    int n = num.size();
    int alast = INT_MAX;
    sort(num.begin(),num.end());
    for(int i = 0;i < n - 3;++i){
        if(num[i] == alast)
            continue;
        int blast = INT_MAX;
        for(int j = i + 1;j < n - 2;++j){
            if(num[j] == blast)
             continue;
            blast = num[j];
            int left = j + 1;
            int newtarget = target - (num[i] + num[j]);
            vector<pair<int,int> > cd = two_sum(num,left,n-1,newtarget);
            vector<pair<int,int> >::const_iterator it = cd.begin();
            for(;it != cd.end(); ++it){
             vector<int> tmp;
             tmp.push_back(num[i]);tmp.push_back(num[j]);
             tmp.push_back(it->first);tmp.push_back(it->second);
             result.push_back(tmp);
            }
        }
        alast = num[i];
    }
    return result;
}