#include <algorithm>
#include <unordered_set>

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        vector<vector<int>> ret;
        unordered_set<unsigned long> retinas;

        if (nums.size() < 3) return ret;

        std::sort(nums.begin(), nums.end());

        for (int i=0; i<nums.size()-2; i++)
        for (int j=i+1; j<nums.size()-1; j++)
        {
            int need = 0 - nums[i] - nums[j];
            auto it = std::lower_bound(nums.begin() + j+1, nums.end(), need);
            if (it != nums.end() && need == *it)
            {
                unsigned long retina = (((unsigned long)nums[i] & 0xFFFFFFFF) << 32) | (((unsigned long)nums[j] & 0xFFFFFFFF));
                if (retinas.find(retina) == retinas.end())
                {
                    ret.push_back({nums[i], nums[j], need});
                    retinas.insert(retina);
                }
            }
        }

        return ret;
    }
};