3 Sum Problem

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;
					// Task performed
					flag = 1;
				}
			}
		}
	}

	// If we reach here, then no triplet was found
	if (flag == 0)
	{
		cout << "Triplet not found";
	}
}

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[0]);

	// 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[0]);
	//calling the function
	numbers(data, size_of_arr, total_sum);
	getch();
}