Four Sum

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)

vector<vector<int> > fourSum(vector<int> &num, int target) {
  vector<vector<int> > result;
  if(num.size() <= 3)
   return result;
  sort(num.begin(), num.end());
  int i = 0;
  while(i < num.size())
  {
   int j = i +1 ;

   while(j < num.size())
   {
   int k = j+1;

   int w = num.size() - 1;
   
   while(k < w )
   {
    bool kinc = false, winc = false;
    if((num[i] + num[j] + num[k] + num[w]) == target)
    {
     vector<int> v;
     v.push_back(num[i]);
     v.push_back(num[j]);
     v.push_back(num[k]);
     v.push_back(num[w]);
     result.push_back(v);
     
     k++;
     w--;
     kinc = true;
     winc = true;
    }
    else if((num[i] + num[j] + num[k] + num[w]) < target)
    {
     k++;
       kinc = true;
    }
    else
    {
     w--;
     winc = true;
    }

    while(kinc && k < w && num[k] == num[k-1])
     k++;

    while(winc && k < w && num[w] == num[w+1])
     w--;
             }

       j++;
       while(j < num.size()  && num[j] == num[j-1])
   j++;
  }

    i++;
     while(i < num.size()  && num[i] == num[i-1])
   i++;

  }

  return result;
}