{"post":"

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>\n#include <conio.h>\n\nvoid findtriplet(int Num[], int size_of_arr, int sum)\n{\n\tint i, k, j, r, flag = 0;\n\t// Fixing the first element of triplet as Num[i]\n\tfor (i = 0; i < size_of_arr - 2; i++)\n\t{\n\t\t// Fixing the second element of triplet as A[j]\n\t\tfor (j = i + 1; j < size_of_arr - 1; j++)\n\t\t{\n\t\t\t// Now fixing the third element of triplet\n\t\t\tfor (k = j + 1; k < size_of_arr; k++)\n\t\t\t{\n\t\t\t \t// Checking for the sum of the triplet\n\t\t\t\tif (Num[i] + Num[j] + Num[k] == sum)\n\t\t\t\t{\n\t\t\t\t\tcout << \"Triplet is \" << Num[i] << \", \" << Num[j] << \", \" << Num[k];\n\t\t\t\t\tcout << endl;\n\t\t\t\t\t// Task performed\n\t\t\t\t\tflag = 1;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\n\t// If we reach here, then no triplet was found\n\tif (flag == 0)\n\t{\n\t\tcout << \"Triplet not found\";\n\t}\n}\n\nvoid main()\n{\n\tclrscr();\n\tint Num[] = { 3, 10, 31, 5, 12, 8 };\n\t/*the values can also be entered by the user using this loop\n\t int n;\n\t cout<<\"enter total number of entries :\";\n\t cin>>n;\n\t cout<<\"Enter the data\\n\";\n\t for(int i=0;i < n;i++)\n\t         cin>>data[i];\n\t */\n\tint sum = 46;\n\tint size_of_arr = sizeof(Num) / sizeof(Num[0]);\n\n\t// function calling\n\tfindtriplet(Num, size_of_arr, sum);\n\tgetch();\n}\n

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>\n#include <conio.h>\n#include <algorithm.h>//for sort()\n\nvoid numbers(int data[], int size_of_arr, int total_sum)\n{\n\tint l, t;\n\t/*Sorting of the elements */\n\tsort(data, data + size_of_arr);\n\n\t/*fixing the first element one by one and find the other two elements using for loop */\n\tfor (int i = 0; i < size_of_arr - 2; i++)\n\t{\n\t\tl = i + 1;\t//index of first element\n\n\t\tt = size_of_arr - 1;\t// index of the last element \n\t\tint flag = 0;\n\t\t//finding the numbers with the help of while loop\n\t\twhile (l < t)\n\t\t{\n\t\t\tif (data[i] + data[l] + data[t] == total_sum)\n\t\t\t{\n\t\t\t\tcout << \"Triplet with sum \" << total_sum << \" is :\" << data[i] << \",                 \" << data[l] << \", \" << data[t] << endl;\n\t\t\t\t//flag will be 1 if the triplet is found in the given data[]\n\t\t\t\tflag = 1;\n\t\t\t}\n\t\t\telse if (data[i] + data[l] + data[t] < total_sum)\n\t\t\t\tl++;\n\t\t\telse\n\t\t\t\tt--;\n\t\t}\n\t}\n\tif (flag == 0)\n\t\tcout << \"No triplet was found\\n\";\n}\n\nvoid main()\n{\n\tclrscr();\n\tint data[] = { 5, 7, 9, 11, 45, 77 };\n\t/*the values can also be entered by the using using this loop\n    \tint n;\n    \tcout<<\"enter total number of entries :\";\n    \tcin>>n;\n    \tcout<<\"Enter the data\\n\";\n    \tfor(int i=0;i < n;i++)\n            \tcin>>data[i];\n    \t*/\n\tint total_sum = 25;\n\t//for user entry use cin>>total_sum\n\tint size_of_arr = sizeof(data) / sizeof(data[0]);\n\t//calling the function\n\tnumbers(data, size_of_arr, total_sum);\n\tgetch();\n}\n

\n","title":"3 Sum Problem","authorDetails":{"name":"studymite","slug":"admin"},"description":"Discover an efficient C++ solution to the classic three sum problem, including both O(n3) and O(n2) time complexity algorithms. Learn how to find all possible groupings of three integers that sum up to either 0 or a specific value (k) in a given list of integers.","slug":"3-sum-problem/","articleId":"636a83447bb1ce5072622b85","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}