Input = [-1, 0, 1, 2, -1, -15, 70], Output: [ [-1, 0, 1], [-1, -1, 2] ]

This problem can be solved in 2 ways:

- Time complexity
**O (n ^ 3)**. - Time complexity
**O(n^2)**.

We shall look into both of the solutions now:

## Solution 1: Iterative method:

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.

## The 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)) // to avoid duplicate elements { // 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; }

## Output:

( -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:

**Step 1:** Sort the given array.

**Step 2:** Our problem is a + b + c = 0, we can modify as b + c = -a.

Here “-a” is the large, and “b” “c”.

## The 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 )

Please write your answers in the comment section of the post below.