问题描述：Givenan 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 containduplicate quadruplets.

  For example, given array S = {1 0 -1 0 -22}, and target = 0.

  A solution set is:

  (-1, 0, 0, 1)

  (-2, -1, 1, 2)

  (-2, 0, 0, 2)

  问题分析：KSum问题，往下最终转化为基本的2Sum问题，同时注意消除重复值即可

  代码：

  java解法：

  ?

  public class Solution {
      public List
      
       > fourSum(int[] num, int target) {
          List
       
        > result = new ArrayList
        
         >(); if(num == null || num.length <= 3) return result; //先对数组进行排序 Arrays.sort(num); int temp_target = 0;//每一次转化为2Sum问题的目标值 for(int i = 0; i < num.length - 3; i++) { //消除重复值 while((i != 0) && (i < num.length - 3) && (num[i] == num[i - 1])) ++ i; //消除重复值之后一定要注意数组边界的判断，避免出现越界情况 if(i < num.length - 3) { for(int j = i + 1; j < num.length - 2; j++) { while((j != i + 1) && (j < num.length - 2) && (num[j] == num[j - 1])) ++ j; if(j < num.length - 2) { temp_target = target - num[i] - num[j]; int start = j + 1; int end = num.length - 1; while(start < end) { int temp_sum = num[start] + num[end]; if(temp_sum < temp_target) { ++ start; } else if(temp_sum > temp_target) { -- end; } else { List
         
           list = new ArrayList<>(); list.add(num[i]); list.add(num[j]); list.add(num[start++]); list.add(num[end--]); result.add(list); //继续往前搜索，并消除相同值 while((start < end) && (num[start] == num[start - 1])) ++ start; while((start < end) && (num[end] == num[end + 1])) -- end; } } } } } } return result; } }
         
        
       
      

  class Solution {
  public:
      vector
      
        > fourSum(vector
       
         &num, int target) { // Note: The Solution object is instantiated only once. vector
        
         > res; int numlen = num.size(); if(num.size()<4) return res; sort(num.begin(),num.end()); set
         
          > tmpres; for(int i = 0; i < numlen; i++) { for(int j = i+1; j < numlen; j++) { int begin = j+1; int end = numlen-1; while(begin < end) { int sum = num[i]+ num[j] + num[begin] + num[end]; if(sum == target) { vector
          
            tmp; tmp.push_back(num[i]); tmp.push_back(num[j]); tmp.push_back(num[begin]); tmp.push_back(num[end]); tmpres.insert(tmp); begin++; end--; }else if(sum
           
            >::iterator it = tmpres.begin(); for(; it != tmpres.end(); it++) res.push_back(*it); return res; } };
           
          
         
        
       
      

  
  
  

  ?

  ?

  ?