I’m working on solving the 3Sum problem, where I need to find all unique triplets in an array that sum up to zero. I’m currently using an unordered_map to store elements and then check for triplets. However, I need help with efficiently removing duplicate triplets from my results.

Output

3-Sum

Here’s my current implementation:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        if(nums.size() < 3) return {};
        
        sort(nums.begin(), nums.end());

        unordered_map<int, int> mp;
        vector<vector<int>> twoD;

        for(int i = 0; i < nums.size(); i++) { 

            for(int j = 0; j < i; j++) {

                    for(int k = 0; k < j; k++) {

                        if(mp.find(j) != mp.end() && mp.find(k) != mp.end() && mp[j] + nums[i] + mp[k] == 0) 
                                twoD.push_back({mp[k], mp[j], nums[i]});
                        
                }
            }   
            mp[i] = nums[i]; 
        }
        reverse(twoD.begin(), twoD.end());
        return twoD;
    }
};

I would like to modify this implementation to ensure that duplicate triplets are not included in the final result. I’ve tried various methods but haven’t been successful in eliminating all duplicates.

Can anyone suggest an efficient way to handle duplicate triplets in this context? Is there a better approach or optimization that I can apply to my current solution to achieve this?

Thank you!