<p>Given an integer array nums, return all the triplets <code>[nums[i], nums[j], nums[k]]</code> such that <code>i != j</code>, <code>i != k</code>, and <code>j != k</code>, and <code>nums[i] + nums[j] + nums[k] == 0</code>.</p>

<p>Notice that the solution set must not contain duplicate triplets.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1,0,1,2,-1,-4]
<strong>Output:</strong> [[-1,-1,2],[-1,0,1]]
<strong>Explanation:</strong> 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [0,1,1]
<strong>Output:</strong> []
<strong>Explanation:</strong> The only possible triplet does not sum up to 0.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [0,0,0]
<strong>Output:</strong> [[0,0,0]]
<strong>Explanation:</strong> The only possible triplet sums up to 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= nums.length &lt;= 3000</code></li>
	<li><code>-10<sup>5</sup> &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // vector<vector<int>> ans;
        // set<vector<int>> s1;
        // for(int i=0;i<nums.size();i++)
    //     {
    //         for(int j=i+1;j<nums.size();j++)
    //         {
    //             for(int k=j+1;k<nums.size();k++)
    //             {
    //                 if(nums[i]+nums[j]+nums[k]==0)
    //                 {
    //                       vector<int> temp={nums[i],nums[j],nums[k]};
    //                       sort(temp.begin(),temp.end());
    //                       s1.insert(temp);
    //                 }
    //             }
    //         }
    //     }
    //    for(auto it:s1)
    //    {
    //     ans.push_back(it);
    //    }
    //    return ans;
//    vector< vector<int> >ans;
//     set<vector<int>> temp;
//     for(int i=0;i<nums.size();i++){
//         unordered_map<int,int> umap;
//         for(int j=i+1;j<nums.size();j++)
//         {
//             int t=-(nums[i]+nums[j]);
//             if(umap.find(t)!=umap.end()){
//                 vector<int> temp2={nums[i],nums[j],t};
//                 sort(temp2.begin(),temp2.end());
//                 temp.insert(temp2);
//             }
//           umap.insert({nums[j],j});

//         }
//     }

//      for(auto it: temp){
//         ans.push_back(it);
//      }
//      return ans;
 vector<vector<int>> ans;
 set<vector<int>> s1;
 sort(nums.begin(),nums.end());
 for(int i=0;i<nums.size();i++)
 {
    if(i>0&&nums[i]==nums[i-1])
    {
        continue;
    }
    int s=i+1;
    int e=nums.size()-1;
    while(s<e)
    {
      int sum=nums[i]+nums[s]+nums[e];
      if(sum<0)
      {
       s++;  
      }
      else if(sum>0)
      {
       e--;
      }
      else{
       vector<int> temp={nums[i],nums[s],nums[e]};
        s1.insert(temp);
        s++;
        e--;
        // while(s<e&&nums[s]!=nums[s-1]){
        //     s++;
        // }
        // while(s<e&&nums[e]!=nums[e+1]){
        //     e--;
        // }
        
      }

    }
 }
   for(auto it:s1 )
   {
    ans.push_back(it);
   }
  return ans;
    }

};
41989