4Sum [Leetcode]

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)

Solution: based on 2sum problem; remember to remove duplicates; time complexity is O(n^3) and space complexity is O(1). [we also can compute the sum of each pair of two elements and store them in a hashtable, this way we can get O(n^2) of time complexity, but the space complexity is increased to O(n^2)]

class Solution {
public:
    void twoSum(vector<int> num, int begin, int first, int second, int target, vector<vector<int> >& r){
        if(begin >= (num.size()-1)) return;
        int b = begin;
        int e = num.size()-1;
        while(b<e){
            if(num[b]+num[e]==target){
                vector<int> subR;
                subR.push_back(first);
                subR.push_back(second);
                subR.push_back(num[b]);
                subR.push_back(num[e]);
                r.push_back(subR);
                //remove duplicates
                do{++b;} while(b<e && num[b]==num[b-1]);
                do{--e;} while(b<e && num[e]==num[e+1]);
            }
            else if(num[b]+num[e]<target)
                ++b;
            else
                --e;
        }
    }
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int>> ret;
        if(num.size()<4)
            return ret;
        sort(num.begin(), num.end());
        for(int i=0; i<num.size()-3; ++i){
            //remove duplicates
            if(i!=0 && num[i]==num[i-1])
                continue;
            for(int j=i+1; j<num.size()-2; j++){
                //remove duplicates
                if(j!=i+1 && num[j]==num[j-1])
                    continue;
                twoSum(num, j+1, num[i], num[j], target-(num[i]+num[j]), ret);
            }
        }
        return ret;        
    }
};