Given an array, find 3 elements such that [a + b + c] = 0. Find all the 3 unique elements.

Input = [-1, 0, 1, 2, -1, -4],

[
  [-1, 0, 1],
  [-1, -1, 2]
]

We shall look into both of the solutions now:

The solution here is simple, we take 3 pointers in 3 for loops, i, j, k.

Where

i starts from base index,

j is i + 1

k is j + 1

We recursively check for the value, then list out the values, whose sum is equal to zero.

Let us consider the array [-8, -7, 5, 2]

Pass 0:
	i = 0, j = 1, k = 2
	-8 -7 + 5 = -10

	i = 0, j = 1, k = 3
	-8 -7 + 2 = -13

	i = 0, j = 2, k = 3
	-8 + 5 + 2 = -1

Pass 1:
	i = 1, j = 2, k = 3
	-7 + 5 + 2 = 0

We got our solution.

Iterative solution in C++

#include<iostream>
#include <vector>

using namespace std;

vector<vector<int> > threeSumIterativeSolution (vector<int>& input_set)
{

	vector<vector<int> >   final_result_set;

		for (int i = 0; i < input_set.size(); i++) 
		{
			for(int j = i + 1; j < input_set.size(); j++) 
			{
				for(int k = i + 2; k < input_set.size(); k++) 
				{
				
					if(j == k || i == j || i ==k) {
						break;
					}


					if(input_set[i] + input_set[j] + input_set[k] == 0  && !(j == k  || k == i)) 
					{
						// if above condition is true, then save it in intermediate vector.
    					vector<int> current_combination;
						current_combination.push_back(input_set[i]);
						current_combination.push_back(input_set[j]);
						current_combination.push_back(input_set[k]);

						// then transfer the intermediate vector to final vector
						final_result_set.push_back(current_combination);					
					}
				}
			}
		}

	return final_result_set;
}




int main()
{
    vector<int> input_set;

    input_set.push_back(-1);
    input_set.push_back(0);
    input_set.push_back(1);
    input_set.push_back(2);
    input_set.push_back(-1);
    input_set.push_back(-4);


     
    vector<vector<int> > final_set =  threeSumIterativeSolution(input_set);

    // If final_set is empty, then
    if (final_set.size() == 0)
    {
        cout << "No possible combinations found";
        return 0;
    }
 
    // print the output
    for (int i = 0; i < final_set.size(); i++)
    {
        if (final_set[i].size() > 0)
        {
            cout << " ( ";
            for (int j = 0; j < final_set[i].size(); j++)
                cout << final_set[i][j] << " ";
            cout << ")";
        }
        cout<<endl;
    }

	return 0;
}

( -1 0 1 )
( -1 -1 2 )
( 0 1 -1 )

As we are using 3 for loops, hence we get time complexity of O (n^3)

Solution 2:

This solution is a subset of “two sum” example. I recommend you to check that solution first, then solve this problem.

Step 1: Sort the given array.

Step 2: Out problem is a + b + c = 0, we can modify as b + c = -a.
Here “-a” is the target, and “b” “c”. Hence we can solve this problem by using 2 sum solution.

Solution in C++

#include<iostream>
#include <vector>

using namespace std;

vector<vector<int> > threeSumWithThreePointers (vector<int>& input_set)
{

	vector<vector<int> >   final_result_set;

    sort(input_set.begin(), input_set.end());

    for (int i = 0; i < input_set.size(); i++) 
    {
        
        int target = -input_set[i]; // set it to inverse of the first number
        int front = i + 1; //front pointer
        int back = input_set.size() - 1; // back pointer
        
        if (i > 0 && input_set[i] == input_set[i - 1]) continue; // if there is duplicates for the first pointer

        // two sum solution with front and back pointers and a target element
        while (front < back) 
        {

            int sum = input_set[front] + input_set[back];
            
            if (sum < target)
                front++;

            else if (sum > target)
                back--;

            else 
            {
                vector<int> current_combination(3, 0);
                current_combination[0] = input_set[i];
                current_combination[1] = input_set[front];
                current_combination[2] = input_set[back];
                final_result_set.push_back(current_combination);
                
                // Processing duplicates of pointer 2
                while (front < back && input_set[front] == current_combination[1]) front++;

                // Processing duplicates of pointer 3
                while (front < back && input_set[back] == current_combination[2]) back--;
            }
            
        }
    }
    

	return final_result_set;
}



int main()
{
    vector<int> input_set;

    input_set.push_back(-1);
    input_set.push_back(0);
    input_set.push_back(1);
    input_set.push_back(2);
    input_set.push_back(-1);
    input_set.push_back(-4);


     
    vector<vector<int> > final_set =  threeSumWithThreePointers(input_set);

    // If final_set is empty, then
    if (final_set.size() == 0)
    {
        cout << "No possible combinations found";
        return 0;
    }
 
    // print the output
    for (int i = 0; i < final_set.size(); i++)
    {
        if (final_set[i].size() > 0)
        {
            cout << " ( ";
            for (int j = 0; j < final_set[i].size(); j++)
                cout << final_set[i][j] << " ";
            cout << ")";
        }
        cout<<endl;
    }

	return 0;
}

Output:

( -1 -1 2 )
( -1 0 1 )