Explore
ProGrad Programs
Placement Prep
TCS Codevita
Webinars
About Us

Edit
Reply




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







If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in