The problem is taken from 15. 3Sum.

Naive Approach

Naive approach would be to go through all possible triplets in the array. And use set data structure to remove duplicates.

Code -

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();

        set<vector<int>> ans;

        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                for(int k=j+1; k<n; k++) {
                    if(nums[i] + nums[j] + nums[k]==0) {
                        vector<int> temp{nums[i], nums[j], nums[k]};
                        sort(temp.begin(), temp.end());
                        ans.insert(temp);
                    }
                }
            }
        }

        vector<vector<int>> ret;
        for(auto itr = ans.begin(); itr != ans.end(); itr++) {
            ret.push_back(*itr);
        }

        return ret;
    }
};

Complexities -

Time complexity - O(n^3)

Space complexity - O(n)

Optimal approach

We use 2-pointers method in this approach. We need to find a, b, c such that a+b+c = 0. So we can fix 'a' just by iterating through the array. To make the sum equal to zero we need two more numbers 'b' and 'c' with sum b+c = -a. That's where we use two pointers.

vector<vector<int>> threeSum(vector<int> &num) {

    vector<vector<int>> res;

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

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

        int target = -num[i];
        int front = i + 1;
        int back = num.size() - 1;

        while (front < back) {

            int sum = num[front] + num[back];

            // Finding answer which start from number num[i]
            if (sum < target)
                front++;

            else if (sum > target)
                back--;

            else {
                vector<int> triplet = {num[i], num[front], num[back]};
                res.push_back(triplet);

                // Processing duplicates of second number
                // Rolling the front pointer to the next different number forwards
                while (front < back && num[front] == triplet[1]) front++;

                // Processing duplicates of third number
                // Rolling the back pointer to the next different number backwards
                while (front < back && num[back] == triplet[2]) back--;
            }

        }

        // Processing duplicates of first number
        while (i + 1 < num.size() && num[i + 1] == num[i]) 
            i++;

    }

    return res;

}

Complexities -

Time complexity - O(n^2)

Space complexity - O(1), not considering the space used to store final value.