Explore
Placement Prep

Edit

Edit

# Find all Triplets with the given sum in the given array | FACE Prep

Published on 10 Mar 2020

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
C++
Java
Python 3

Output
Enter the number of elements : 5
Input the array elements : 0 -1 2 -3 1
Enter the sum value : -2
The triplets are :
-3 -1 2
-3 0 1

## 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)
• Check if the sum of arr[i], arr[p] and arr[q] is equal to the sum_value.
• 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++
Java
Python 3

Output
Enter the number of elements : 5
Input the array elements : 0 -1 2 -3 1
Enter the sum value : -2
The triplets are :
-3 -1 2
-3 0 1

## 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.
• sum = arr[i] + arr[j]
• if (-sum) is present in the hash table,
• then print arr[i], arr[j] and -sum as triplets.
• 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

C++

Output
Enter the number of elements : 5
Input the array elements : 0 -1 2 -3 1
Enter the sum value : -2
The triplets are :
-3 -1 2
-3 0 1

Recommended Programs