# 3 Sum Problem

Written By -

3 sum is a simple problem on the face of it, but there are a couple of things that make it tricky:

• Ensuring no duplicate outputs.
• Creating the O(n2) solution instead of the O(n3) straightforward solution.

We take a list of integers and return possible groupings of three integers that sum up to either 0 or any specific number (k).

EX-

SUM = 0

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

A solution set is: [ [1, 0, -1], [2, -2, 0] ]

SUM = K

Input: [2, 7, 11, 15, 3] , Sum: 20.

A solution set is: [ [2, 7, 11], [2, 15, 3] ]

## # Brute Force

``````#include <iostream.h>
#include <conio.h>

void findtriplet(int Num[], int size_of_arr, int sum)
{
int i, k, j, r, flag = 0;
// Fixing the first element of triplet as Num[i]
for (i = 0; i < size_of_arr - 2; i++)
{
// Fixing the second element of triplet as A[j]
for (j = i + 1; j < size_of_arr - 1; j++)
{
// Now fixing the third element of triplet
for (k = j + 1; k < size_of_arr; k++)
{
// Checking for the sum of the triplet
if (Num[i] + Num[j] + Num[k] == sum)
{
cout << "Triplet is " << Num[i] << ", " << Num[j] << ", " << Num[k];
cout << endl;
flag = 1;
}
}
}
}

// If we reach here, then no triplet was found
if (flag == 0)
{
}
}

void main()
{
clrscr();
int Num[] = { 3, 10, 31, 5, 12, 8 };
/*the values can also be entered by the user using this loop
int n;
cout<<"enter total number of entries :";
cin>>n;
cout<<"Enter the data\n";
for(int i=0;i < n;i++)
cin>>data[i];
*/
int sum = 46;
int size_of_arr = sizeof(Num) / sizeof(Num);

// function calling
findtriplet(Num, size_of_arr, sum);
getch();
}``````

The Time Complexity of the above code is O(n3).

But the Time Complexity can be reduced to O(n2) and code can be optimized by using the sorting method.

## # Optimised Approach

``````#include <iostream.h>
#include <conio.h>
#include <algorithm.h>//for sort()

void numbers(int data[], int size_of_arr, int total_sum)
{
int l, t;
/*Sorting of the elements */
sort(data, data + size_of_arr);

/*fixing the first element one by one and find the other two elements using for loop */
for (int i = 0; i < size_of_arr - 2; i++)
{
l = i + 1;	//index of first element

t = size_of_arr - 1;	// index of the last element
int flag = 0;
//finding the numbers with the help of while loop
while (l < t)
{
if (data[i] + data[l] + data[t] == total_sum)
{
cout << "Triplet with sum " << total_sum << " is :" << data[i] << ",                 " << data[l] << ", " << data[t] << endl;
//flag will be 1 if the triplet is found in the given data[]
flag = 1;
}
else if (data[i] + data[l] + data[t] < total_sum)
l++;
else
t--;
}
}
if (flag == 0)
cout << "No triplet was found\n";
}

void main()
{
clrscr();
int data[] = { 5, 7, 9, 11, 45, 77 };
/*the values can also be entered by the using using this loop
int n;
cout<<"enter total number of entries :";
cin>>n;
cout<<"Enter the data\n";
for(int i=0;i < n;i++)
cin>>data[i];
*/
int total_sum = 25;
//for user entry use cin>>total_sum
int size_of_arr = sizeof(data) / sizeof(data);
//calling the function
numbers(data, size_of_arr, total_sum);
getch();
}``````

Related Posts: