vector<vector<int>> ThreeSum(vector<int>& nums) 
{
  vector<vector<int>> output;
  sort(nums.begin(), nums.end());
  for (int i = 0; i < nums.size(); ++i) 
  {
    // Never let i refer to the same value twice to avoid duplicates.
    //Check if the next value is the same as the previous value
    if (i != 0 && nums[i] == nums[i - 1]) continue;

    int j = i + 1;
    int k = nums.size() - 1;
    while (j < k) 
    {
      if (nums[i] + nums[j] + nums[k] == 0) 
      {
        output.push_back({nums[i], nums[j], nums[k]});
        ++j;
        // Never let j refer to the same value twice (in an output) to avoid duplicates
        // Make sure next value is not same as the first value
        while (j < k && nums[j] == nums[j-1])
        {
          ++j;
        }
      } 
      else if (nums[i] + nums[j] + nums[k] < 0) 
      {
        ++j;
      } 
      else 
      {
        --k;
      }
    }
}
return output;
}