3 SUM

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ? b ? c)
• The solution set must not contain duplicate triplets.

  vector<vector<int> > threeSum(vector<int> &num) {
  vector<vector<int> > result;
  if(num.size() <= 2)
   return result;
  sort(num.begin(), num.end());
  int i = 0;
  while(i < num.size())
  {
   int j = i +1 ;
   int k = num.size() - 1;
   while(j < k )
   {
    bool jinc = false, kinc = false;
    if(num[i] + num[j] + num[k] == 0)
    {
     vector<int> v;
     v.push_back(num[i]);
     v.push_back(num[j]);
     v.push_back(num[k]);
     result.push_back(v);
     j++;
     k--;
     jinc = true;
     kinc = true;
    }
    else if((num[i] + num[j] + num[k]) > 0)
    {
     k--;
                   kinc = true;
    }
    else
    {
     j++;
     jinc = true;
    }

    while(jinc && j < k && num[j] == num[j-1])
     j++;

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

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

  return result;
}