LeetCode 18 4Sum

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)

第一想法是利用3sum的算法，在s中选出一个数elem，求出res=target-elem,然后在剩下的元素中利用3sum的方法查找，但是实现的时候出现了重复，
例如target = 0时， elem= -1，此时res= 1， 能够找到-1 0 0 1， 但是elem=1时，也能找到 -1 0 0 1，如何删除这种重复？
最终实现网上提供的方法，先排序，在按照顺序， 利用分治法来查找。

 vector<vector<int>> fourSum(vector<int>& nums, int target) 
{
    vector<vector<int>> ret;
    int iPrevious = 0;
    if(nums.size() < 4)
    {
        return ret;
    }
    vector<int> mid(4, 0);
    set<string> intSet;

    insertsort3(nums);
    for(int j = 0; j!= nums.size() -3 ; ++j)
    {
        mid[0] = nums[j];
        
        for(int i = j+1; i!= nums.size() -2; ++i)
        {
           mid[1] = nums[i];
           int res = target  -  mid[0] - mid[1];
           int p = i+1;
           int q = nums.size()-1;
            while(p < q)
            {
                int s3 = nums[p] + nums[q];
    
                if(res < s3)
                {
                    --q;
                }
                else if(res > s3)
                {
                    ++p;
                }
                else
                {
                    string str;
                    str += mid[0];
                    str += mid[1];
                    str += nums[p];
                    str += nums[q];
                    set<string>::iterator iter = intSet.find(str);
                    if(iter == intSet.end())
                    {
                        intSet.insert(str);
                        mid[2] = nums[p];
                        mid[3] = nums[q];
                        ret.push_back(mid);
                    }
                    ++p  ;
                    --q  ; 
                }
            }
        }
    }
    return ret;
}
void insertsort3(vector<int> &nums)
{
    int j = 0;

    for(int i= 1; i != nums.size(); i++)
    {
        int temp = nums[i];
        for(j=i; j>0 && temp < nums[j-1]; --j)
        {
            nums[j] = nums[j-1];
        }
        nums[j] = temp;
    }
}

排序算法是个基础。