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一样

class Solution {public:    vector
     
      
        > fourSum(vector
       
         &num, int target) {        vector
        
         
           > res;        int n = num.size();        if( n < 4) return res;        sort(num.begin(),num.end());        for(int i = 0; i < n-3; ++ i){            if(i !=0 && num[i]== num[i-1]) continue;            for(int j = i+1; j < n-2; ++ j){                if(j!=i+1 && num[j] == num[j-1] ) continue;                int start = j+1, end = n-1;                while(start < end){                    int sum = num[i]+num[j]+num[start]+num[end];                    if(sum > target) end--;                    else if(sum < target) start++;                    else{                        vector
          
            a; a.push_back(num[i]);a.push_back(num[j]); a.push_back(num[start]);a.push_back(num[end]); res.push_back(a); do{start++;}while(start < end && num[start] == num[start-1]); do{end--;}while(start < end && num[end] == num[end+1]); } } } } return res; }};