Triplet Sum in Array (3sum)
Last Updated :
17 Oct, 2023
Given an array arr[] of size n and an integer X. Find if there’s a triplet in the array which sums up to the given integer X.
Examples:
Input: array = {12, 3, 4, 1, 6, 9}, sum = 24;
Output: 12, 3, 9
Explanation: There is a triplet (12, 3 and 9) present
in the array whose sum is 24.
Input: array = {1, 2, 3, 4, 5}, sum = 9
Output: 5, 3, 1
Explanation: There is a triplet (5, 3 and 1) present
in the array whose sum is 9.
Triplet Sum in Array (3sum) by generating all the triplets:
A simple method is to generate all possible triplets and compare the sum of every triplet with the given value. The following code implements this simple method using three nested loops.
Step-by-step approach:
- Given an array of length n and a sum s
- Create three nested loop first loop runs from start to end (loop counter i), second loop runs from i+1 to end (loop counter j) and third loop runs from j+1 to end (loop counter k)
- The counter of these loops represents the index of 3 elements of the triplets.
- Find the sum of ith, jth and kth element. If the sum is equal to given sum. Print the triplet and break.
- If there is no triplet, then print that no triplet exist.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
bool find3Numbers(int A[], int arr_size, int sum)
{
for (int i = 0; i < arr_size - 2; i++)
{
for (int j = i + 1; j < arr_size - 1; j++)
{
for (int k = j + 1; k < arr_size; k++)
{
if (A[i] + A[j] + A[k] == sum)
{
cout << "Triplet is " << A[i] <<
", " << A[j] << ", " << A[k];
return true;
}
}
}
}
return false;
}
int main()
{
int A[] = { 1, 4, 45, 6, 10, 8 };
int sum = 22;
int arr_size = sizeof(A) / sizeof(A[0]);
find3Numbers(A, arr_size, sum);
return 0;
}
|
C
#include <stdio.h>
bool find3Numbers(int A[], int arr_size, int sum)
{
int l, r;
for (int i = 0; i < arr_size - 2; i++) {
for (int j = i + 1; j < arr_size - 1; j++) {
for (int k = j + 1; k < arr_size; k++) {
if (A[i] + A[j] + A[k] == sum) {
printf("Triplet is %d, %d, %d",
A[i], A[j], A[k]);
return true;
}
}
}
}
return false;
}
int main()
{
int A[] = { 1, 4, 45, 6, 10, 8 };
int sum = 22;
int arr_size = sizeof(A) / sizeof(A[0]);
find3Numbers(A, arr_size, sum);
return 0;
}
|
Java
class FindTriplet {
boolean find3Numbers(int A[], int arr_size, int sum)
{
int l, r;
for (int i = 0; i < arr_size - 2; i++) {
for (int j = i + 1; j < arr_size - 1; j++) {
for (int k = j + 1; k < arr_size; k++) {
if (A[i] + A[j] + A[k] == sum) {
System.out.print("Triplet is " + A[i] + ", " + A[j] + ", " + A[k]);
return true;
}
}
}
}
return false;
}
public static void main(String[] args)
{
FindTriplet triplet = new FindTriplet();
int A[] = { 1, 4, 45, 6, 10, 8 };
int sum = 22;
int arr_size = A.length;
triplet.find3Numbers(A, arr_size, sum);
}
}
|
Python3
def find3Numbers(A, arr_size, sum):
for i in range( 0, arr_size-2):
for j in range(i + 1, arr_size-1):
for k in range(j + 1, arr_size):
if A[i] + A[j] + A[k] == sum:
print("Triplet is", A[i],
", ", A[j], ", ", A[k])
return True
return False
A = [1, 4, 45, 6, 10, 8]
sum = 22
arr_size = len(A)
find3Numbers(A, arr_size, sum)
|
C#
using System;
class GFG {
static bool find3Numbers(int[] A,
int arr_size,
int sum)
{
for (int i = 0;
i < arr_size - 2; i++) {
for (int j = i + 1;
j < arr_size - 1; j++) {
for (int k = j + 1;
k < arr_size; k++) {
if (A[i] + A[j] + A[k] == sum) {
Console.WriteLine("Triplet is " + A[i] + ", " + A[j] + ", " + A[k]);
return true;
}
}
}
}
return false;
}
static public void Main()
{
int[] A = { 1, 4, 45, 6, 10, 8 };
int sum = 22;
int arr_size = A.Length;
find3Numbers(A, arr_size, sum);
}
}
|
Javascript
<script>
function find3Numbers(A, arr_size, sum)
{
let l, r;
for (let i = 0; i < arr_size - 2; i++)
{
for (let j = i + 1; j < arr_size - 1; j++)
{
for (let k = j + 1; k < arr_size; k++)
{
if (A[i] + A[j] + A[k] == sum)
{
document.write("Triplet is " + A[i] +
", " + A[j] + ", " + A[k]);
return true;
}
}
}
}
return false;
}
let A = [ 1, 4, 45, 6, 10, 8 ];
let sum = 22;
let arr_size = A.length;
find3Numbers(A, arr_size, sum);
</script>
|
PHP
<?php
function find3Numbers($A, $arr_size, $sum)
{
$l; $r;
for ($i = 0;
$i < $arr_size - 2; $i++)
{
for ($j = $i + 1;
$j < $arr_size - 1; $j++)
{
for ($k = $j + 1;
$k < $arr_size; $k++)
{
if ($A[$i] + $A[$j] +
$A[$k] == $sum)
{
echo "Triplet is", " ", $A[$i],
", ", $A[$j],
", ", $A[$k];
return true;
}
}
}
}
return false;
}
$A = array(1, 4, 45,
6, 10, 8);
$sum = 22;
$arr_size = sizeof($A);
find3Numbers($A, $arr_size, $sum);
?>
|
Output
Triplet is 4, 10, 8
Complexity Analysis:
- Time Complexity: O(n3), There are three nested loops traversing the array, so the time complexity is O(n^3)
- Auxiliary Space: O(1), As no extra space is required.
By Sorting the array the efficiency of the algorithm can be improved. This efficient approach uses the two-pointer technique. Traverse the array and fix the first element of the triplet. Now use the Two Pointers algorithm to find if there is a pair whose sum is equal to x – array[i]. Two pointers algorithm take linear time so it is better than a nested loop.
Step-by-step approach:
- Sort the given array.
- Loop over the array and fix the first element of the possible triplet, arr[i].
- Then fix two pointers, one at i + 1 and the other at n – 1. And look at the sum,
- If the sum is smaller than the required sum, increment the first pointer.
- Else, If the sum is bigger, Decrease the end pointer to reduce the sum.
- Else, if the sum of elements at two-pointer is equal to given sum then print the triplet and break.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
bool find3Numbers(int A[], int arr_size, int sum)
{
int l, r;
sort(A, A + arr_size);
for (int i = 0; i < arr_size - 2; i++) {
l = i + 1;
r = arr_size - 1;
while (l < r) {
if (A[i] + A[l] + A[r] == sum) {
printf("Triplet is %d, %d, %d", A[i], A[l],A[r]);
return true;
}
else if (A[i] + A[l] + A[r] < sum)
l++;
else
r--;
}
}
return false;
}
int main()
{
int A[] = { 1, 4, 45, 6, 10, 8 };
int sum = 22;
int arr_size = sizeof(A) / sizeof(A[0]);
find3Numbers(A, arr_size, sum);
return 0;
}
|
C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int cmpfunc(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
bool find3Numbers(int A[], int arr_size, int sum)
{
int l, r;
qsort(A, arr_size, sizeof(int), cmpfunc);
for (int i = 0; i < arr_size - 2; i++)
{
l = i + 1;
r = arr_size - 1;
while (l < r) {
if (A[i] + A[l] + A[r] == sum) {
printf("Triplet is %d, %d, %d", A[i], A[l],
A[r]);
return true;
}
else if (A[i] + A[l] + A[r] < sum)
l++;
else
r--;
}
}
return false;
}
int main()
{
int A[] = { 1, 4, 45, 6, 10, 8 };
int sum = 22;
int arr_size = sizeof(A) / sizeof(A[0]);
find3Numbers(A, arr_size, sum);
return 0;
}
|
Java
class FindTriplet {
boolean find3Numbers(int A[], int arr_size, int sum)
{
int l, r;
quickSort(A, 0, arr_size - 1);
for (int i = 0; i < arr_size - 2; i++) {
l = i + 1;
r = arr_size - 1;
while (l < r) {
if (A[i] + A[l] + A[r] == sum) {
System.out.print("Triplet is " + A[i] + ", " + A[l] + ", " + A[r]);
return true;
}
else if (A[i] + A[l] + A[r] < sum)
l++;
else
r--;
}
}
return false;
}
int partition(int A[], int si, int ei)
{
int x = A[ei];
int i = (si - 1);
int j;
for (j = si; j <= ei - 1; j++) {
if (A[j] <= x) {
i++;
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
int temp = A[i + 1];
A[i + 1] = A[ei];
A[ei] = temp;
return (i + 1);
}
void quickSort(int A[], int si, int ei)
{
int pi;
if (si < ei) {
pi = partition(A, si, ei);
quickSort(A, si, pi - 1);
quickSort(A, pi + 1, ei);
}
}
public static void main(String[] args)
{
FindTriplet triplet = new FindTriplet();
int A[] = { 1, 4, 45, 6, 10, 8 };
int sum = 22;
int arr_size = A.length;
triplet.find3Numbers(A, arr_size, sum);
}
}
|
Python3
def find3Numbers(A, arr_size, sum):
A.sort()
for i in range(0, arr_size-2):
l = i + 1
r = arr_size-1
while (l < r):
if( A[i] + A[l] + A[r] == sum):
print("Triplet is", A[i],
', ', A[l], ', ', A[r]);
return True
elif (A[i] + A[l] + A[r] < sum):
l += 1
else:
r -= 1
return False
A = [1, 4, 45, 6, 10, 8]
sum = 22
arr_size = len(A)
find3Numbers(A, arr_size, sum)
|
C#
using System;
class GFG {
bool find3Numbers(int[] A, int arr_size,
int sum)
{
int l, r;
quickSort(A, 0, arr_size - 1);
for (int i = 0; i < arr_size - 2; i++) {
l = i + 1;
r = arr_size - 1;
while (l < r) {
if (A[i] + A[l] + A[r] == sum) {
Console.Write("Triplet is " + A[i] + ", " + A[l] + ", " + A[r]);
return true;
}
else if (A[i] + A[l] + A[r] < sum)
l++;
else
r--;
}
}
return false;
}
int partition(int[] A, int si, int ei)
{
int x = A[ei];
int i = (si - 1);
int j;
for (j = si; j <= ei - 1; j++) {
if (A[j] <= x) {
i++;
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
int temp1 = A[i + 1];
A[i + 1] = A[ei];
A[ei] = temp1;
return (i + 1);
}
void quickSort(int[] A, int si, int ei)
{
int pi;
if (si < ei) {
pi = partition(A, si, ei);
quickSort(A, si, pi - 1);
quickSort(A, pi + 1, ei);
}
}
static void Main()
{
GFG triplet = new GFG();
int[] A = new int[] { 1, 4, 45, 6, 10, 8 };
int sum = 22;
int arr_size = A.Length;
triplet.find3Numbers(A, arr_size, sum);
}
}
|
Javascript
<script>
function find3Numbers(A, arr_size, sum)
{
let l, r;
A.sort((a,b) => a-b);
for (let i = 0; i < arr_size - 2; i++) {
l = i + 1;
r = arr_size - 1;
while (l < r) {
if (A[i] + A[l] + A[r] == sum)
{
document.write("Triplet is " + A[i] + ", "
+ A[l] + ", " + A[r]);
return true;
}
else if (A[i] + A[l] + A[r] < sum)
l++;
else
r--;
}
}
return false;
}
let A = [ 1, 4, 45, 6, 10, 8 ];
let sum = 22;
let arr_size = A.length;
find3Numbers(A, arr_size, sum);
</script>
|
PHP
<?php
function find3Numbers($A, $arr_size, $sum)
{
$l; $r;
sort($A);
for ($i = 0; $i < $arr_size - 2; $i++)
{
$l = $i + 1;
$r = $arr_size - 1;
while ($l < $r)
{
if ($A[$i] + $A[$l] +
$A[$r] == $sum)
{
echo "Triplet is ", $A[$i], " ",
$A[$l], " ",
$A[$r], "\n";
return true;
}
else if ($A[$i] + $A[$l] +
$A[$r] < $sum)
$l++;
else
$r--;
}
}
return false;
}
$A = array (1, 4, 45, 6, 10, 8);
$sum = 22;
$arr_size = sizeof($A);
find3Numbers($A, $arr_size, $sum);
?>
|
Output
Triplet is 4, 8, 10
Complexity Analysis:
- Time complexity: O(N^2), There are only two nested loops traversing the array, so time complexity is O(n^2). Two pointers algorithm takes O(n) time and the first element can be fixed using another nested traversal.
- Auxiliary Space: O(1), As no extra space is required.
Triplet Sum in Array (3sum) using Hashing:
This approach uses extra space but is simpler than the two-pointers approach. Run two loops outer loop from start to end and inner loop from i+1 to end. Create a hashmap or set to store the elements in between i+1 to n-1. So if the given sum is x, check if there is a number in the set which is equal to x – arr[i] – arr[j]. If yes print the triplet.
Step-by-step approach:
- Iterate through the array, fixing the first element (A[i]) for the triplet.
- For each A[i], use a Hashmap to store potential second elements that complete the desired sum (sum – A[i]).
- Inside a nested loop, check if the difference between the current element (A[j]) and the desired sum (sum – A[i]) is present in the Hashmap. If it is, a triplet is found, then print it.
- If no triplet is found in the entire array, the function returns false.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
bool find3Numbers(int A[], int arr_size, int sum)
{
for (int i = 0; i < arr_size - 2; i++) {
unordered_set<int> s;
int curr_sum = sum - A[i];
for (int j = i + 1; j < arr_size; j++) {
int required_value = curr_sum - A[j];
if (s.find(required_value) != s.end()) {
printf("Triplet is %d, %d, %d", A[i], A[j],
required_value);
return true;
}
s.insert(A[j]);
}
}
return false;
}
int main()
{
int A[] = { 1, 4, 45, 6, 10, 8 };
int sum = 22;
int arr_size = sizeof(A) / sizeof(A[0]);
find3Numbers(A, arr_size, sum);
return 0;
}
|
Java
import java.util.HashSet;
public class TripletSumFinder {
public static boolean
find3Numbers(int[] A, int arr_size, int sum)
{
for (int i = 0; i < arr_size - 2; i++) {
HashSet<Integer> s = new HashSet<>();
int curr_sum = sum - A[i];
for (int j = i + 1; j < arr_size; j++) {
int required_value = curr_sum - A[j];
if (s.contains(required_value)) {
System.out.println("Triplet is " + A[i]
+ ", " + A[j] + ", "
+ required_value);
return true;
}
s.add(A[j]);
}
}
return false;
}
public static void main(String[] args)
{
int[] A = { 1, 4, 45, 6, 10, 8 };
int sum = 22;
int arr_size = A.length;
if (!find3Numbers(A, arr_size, sum)) {
System.out.println(
"No triplet found with the given sum.");
}
}
}
|
Python3
def find3Numbers(arr, sum):
for i in range(len(arr) - 2):
s = set()
curr_sum = sum - arr[i]
for j in range(i + 1, len(arr)):
required_value = curr_sum - arr[j]
if required_value in s:
print(f"Triplet is {arr[i]}, {arr[j]}, {required_value}")
return True
s.add(arr[j])
return False
if __name__ == "__main__":
arr = [1, 4, 45, 6, 10, 8]
target_sum = 22
if not find3Numbers(arr, target_sum):
print("No triplet found.")
|
C#
using System;
using System.Collections.Generic;
class Program {
static bool Find3Numbers(int[] arr, int sum)
{
for (int i = 0; i < arr.Length - 2; i++) {
HashSet<int> s = new HashSet<int>();
int curr_sum = sum - arr[i];
for (int j = i + 1; j < arr.Length; j++) {
int required_value = curr_sum - arr[j];
if (s.Contains(required_value)) {
Console.WriteLine("Triplet is " + arr[i]
+ ", " + arr[j] + ", "
+ required_value);
return true;
}
s.Add(arr[j]);
}
}
return false;
}
static void Main()
{
int[] arr = { 1, 4, 45, 6, 10, 8 };
int target_sum = 22;
if (!Find3Numbers(arr, target_sum)) {
Console.WriteLine("No triplet found.");
}
}
}
|
Javascript
function find3Numbers(A, sum) {
for (let i = 0; i < A.length - 2; i++) {
const s = new Set();
const currSum = sum - A[i];
for (let j = i + 1; j < A.length; j++) {
const requiredValue = currSum - A[j];
if (s.has(requiredValue)) {
console.log(`Triplet is ${A[i]}, ${A[j]}, ${requiredValue}`);
return true;
}
s.add(A[j]);
}
}
return false;
}
function main() {
const A = [1, 4, 45, 6, 10, 8];
const sum = 22;
if (!find3Numbers(A, sum)) {
console.log("No triplet found with the given sum.");
}
}
main();
|
Output
Triplet is 4, 8, 10
Time complexity: O(N^2)
Auxiliary Space: O(N), since n extra space has been taken
You can watch the explanation of the problem on YouTube discussed By Geeks For Geeks Team.
You can also refer this video present on Youtube.
How to print all triplets with given sum?
Refer Find all triplets with zero sum.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...