Find all triplets with the given sum in the given array | faceprep

Program to find all triplets with the given sum in the given array is discussed here. Given an array of integers and a sum value, we need to iterate through the array and find all possible triplets that sum to the given value.

For example,

Consider the array: arr[] = {0, -1, 2, -3, 1}. The given  sum is -2. In the given array, the triplets with sum = -2   are {0, -3, 1} and {-1, 2, -3}.

Method 1:

  • Use three loops and check one by one that sum of three elements is equal to the given sum or not.
  • If the sum of 3 elements is equal to the given sum, then print elements otherwise print not found.

Time complexity: O (n^3)

Program to find all the triplets with the given sum

// C program to find all the triplets with the given sum

#include

void find_all_triplets(int arr[], int n, int sum)
{
for (int i = 0; i < n – 2; i++)
{
for (int j = i + 1; j < n – 1; j++)
{
for (int k = j + 1; k < n; k++)
{
if (arr[i] + arr[j] + arr[k] == sum)
{
printf(“%d,%d,%d\n”,arr[i],arr[j],arr[k]);
}}}}}

int main()
{
int n, sum;
printf(“\nEnter the number of elements : “);
scanf(“%d”,&n);
int arr[n];
printf(“\nInput the array elements : “);
for(int i = 0; i < n; i++)
{
scanf(“%d”,&arr[i]);
}
printf(“\nEnter the sum value : “);
scanf(“%d”,&sum);
printf(“\nThe triplets are \n “);
find_all_triplets(arr, n, sum);
return 0;
}

// C++ program to find all the triplets with the given sum

#include <bits/stdc++.h>
using namespace std;

void find_all_triplets(int arr[], int n, int sum)
{
for (int i = 0; i < n – 2; i++)
{
for (int j = i + 1; j < n – 1; j++)
{
for (int k = j + 1; k < n; k++)
{
if (arr[i] + arr[j] + arr[k] == sum)
{
cout << arr[i] << “,” << arr[j] << “,” << arr[k] <<endl;
}
}
}
}
}

int main()
{
int n, sum;
cout << “\nEnter the number of elements : “;
cin >> n;
int arr[n];
cout << “\nInput the array elements : “;
for(int i = 0; i < n; i++)
{
cin >> arr[i];
}
cout << “\nEnter the sum value : “;
cin >> sum;
cout << “\nThe triplets are \n “;
find_all_triplets(arr, n, sum);
return 0;
}

// Java  program to find all the triplets with the given sum

import java.io.*;

class Main
{

static void find_all_triplets(int arr[], int n, int sum)
{
for (int i = 0; i < n – 2; i++)
{
for (int j = i + 1; j < n – 1; j++)
{
for (int k = j + 1; k < n; k++)
{
if (arr[i] + arr[j] + arr[k] == sum)
{
System.out.println(arr[i]+ ” ” + arr[j] + ” ” + arr[k]);
}
}
}
}
}

public static void main (String[] args)
{
int arr[] = {0, -1, 2, -3, 1};
int n = arr.length;
find_all_triplets(arr, n, -2);
}
}

# Python  program to find all the triplets with the given sum

def find_all_triplets(arr, n, sum):
for i in range(0 , n – 2):
for j in range(i + 1 , n – 1):
for k in range(j + 1, n):
if (arr[i] + arr[j] +
arr[k] == sum):
print(arr[i], ” “,
arr[j] ,” “,
arr[k] , sep = “”)

arr = [ 0, -1, 2, -3, 1 ]
n = len(arr)
sum = -2
find_all_triplets(arr, n, sum)

 

Method 2:

The triplets can be printed using the sorting technique.

  • First, sort the array.
  • Iterate the loop from i = 0 to i = n – 2.
  • Initialize two variables, p = i + 1 and q = n – 1.
  • While (p < q)
  1. Check if the sum of arr[i], arr[p] and arr[q] is equal to the sum_value.
  2. If it is equal, print arr[i], arr[p], arr[q] and perfrom p++ and q–.
  • If the sum is less than the given sum_value, then perform p++.
  • If the sum is greater than the given sum_value, then perform q–.
  • Repeat steps 4 to 6.

Time complexity: O(n^2)

Program to find all the triplets with the given sum using sorting technique

// C++ program to find all the triplets with the given sum

#include <bits/stdc++.h>
using namespace std;

void find_all_triplets(int arr[], int n, int sum)
{
sort(arr, arr + n);

for (int i = 0; i < n – 1; i++)
{
int l = i + 1;
int r = n – 1;
int x = arr[i];
while (l < r) {
if (x + arr[l] + arr[r] == sum)
{
printf(“%d %d %d\n”, x, arr[l], arr[r]);
l++;
r–;
}

else if (x + arr[l] + arr[r] < sum)
l++;


else
r–;
}
}
}

int main()
{
int n, sum;
cout << “\nEnter the number of elements : “;
cin >> n;
int arr[n];
cout << “\nInput the array elements : “;
for(int i = 0; i < n; i++)
{
cin >> arr[i];
}
cout << “\nEnter the sum value : “;
cin >> sum;
cout << “\nThe triplets are \n “;
find_all_triplets(arr, n, sum);
return 0;
}

import java.io.*;
import java.util.*;

class Main
{
static void findTriplets(int[] arr, int n, int sum)
{
Arrays.sort(arr);

for (int i = 0;
i < n – 1; i++)
{
int l = i + 1;
int r = n – 1;
int x = arr[i];
while (l < r)
{
if (x + arr[l] + arr[r] == sum)
{

System.out.println(x + ” ” + arr[l] + ” ” + arr[r]);
l++;
r–;
}

else if (x + arr[l] +
arr[r] < sum)
l++;

else
r–;
}
}
}

public static void main(String args[])
{
int[] arr = new int[]{ 0, -1, 2, -3, 1 };
int sum = -2;
int n = arr.length;
findTriplets(arr, n, sum);
}
}

def findTriplets(arr, n, sum):
arr.sort();
for i in range(0, n – 1):

l = i + 1;
r = n – 1;
x = arr[i];
while (l < r) :
if (x + arr[l] + arr[r] == sum) :

print(x, arr[l], arr[r]);
l = l + 1;
r = r – 1;

elif (x + arr[l] + arr[r] < sum):
l = l + 1;

else:
r = r – 1;

arr = [ 0, -1, 2, -3, 1 ];
sum = -2;
n = len(arr);
findTriplets(arr, n, sum);

Method 3:

Triplets can be found using the hashing technique.

  • Traverse the array from i = 0 to n – 2.
  • Create an empty hash table.
  • Traverse from j =  i+ 1 to n -1.
  1. sum = arr[i] + arr[j]
  2. if (-sum) is present in the hash table,
  3. then print arr[i], arr[j] and -sum as triplets.
  4. else, insert arr[j] in the hash table and proceed.

Time complexity: O(n^2)

Program to find all the triplets with the given sum using hashing technique

#include <bits/stdc++.h>
using namespace std;

void find_all_triplets(int arr[], int n, int sum)
{
for (int i = 0; i < n – 1; i++) {

unordered_set<int> s;
for (int j = i + 1; j < n; j++) {
int x = sum – (arr[i] + arr[j]);
if (s.find(x) != s.end())
printf(“%d %d %d\n”, x, arr[i], arr[j]);
else
s.insert(arr[j]);
}
}
}

int main()
{
int n, sum;
cout << “\nEnter the number of elements : “;
cin >> n;
int arr[n];
cout << “\nInput the array elements : “;
for(int i = 0; i < n; i++)
{
cin >> arr[i];
}
cout << “\nEnter the sum value : “;
cin >> sum;
cout << “\nThe triplets are \n “;
find_all_triplets(arr, n, sum);
return 0;
}

Output:

triplets with the given sum