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.

Solution:
  Since the boundary for k-sum problem is O(n^(k-1)), one of the solution is to use four pointers. Fix the first one, then the other three is a 3sum problem.

O(N^2) solution has to use Hash. 
1. Build a N^2 table  of (i,j) pair , then for different row and column, do addition and remove duplicate.
2. 设数组为arr,一个hashtable t，指针pos 
pos=n-3~0,表示第二个数b的位置，那么c和d在pos+1~n-1，a在0~pos-1 
当每轮迭代时，现将arr[pos+1]与arr[pos+2]~arr[n-1]的和放入t，更新所有c+d的值，然后在0~pos-1中找a，将t[-(arr[a]+arr[pos])]的值加入答案中 

?????????

basic idea is to use space to get time complexity

Code:
vector > fourSum(vector &num, int target) {
   vector > res;
   vector quadr(4,0);
   if (num.size()<4 res="" return="" span="">
  sort(num.begin(), num.end());
  set> ht;
   for(int i=0; i
   {
       for(int j=i+1; j
       {
           
           int k = j+1;
           int l = num.size()-1;
           while(k
           {
              int fsum = num[i]+num[j]+num[k]+num[l];
              if (fsum ==target)
              {
                  quadr[0]=num[i];
                  quadr[1]=num[j];
                  quadr[2]=num[k];
                  quadr[3]=num[l];
                  if (ht.find(quadr)==ht.end())
                  {
                      res.push_back(quadr);
                      ht.insert(quadr);
                  }
                  k++;
                  l--;
              }
              else
              {
                  if (fsum>target)
                    l--;
                  else
                    k++;
              }
           }
       }
   }
   return res;

}