The 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 the 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

@@coding::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 the sorting technique

@@coding::2@@

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 a hashing technique

@@coding::3@@

Recommended Programs

• Minimum scalar product of two vectors

• Maximum scalar product of two vectors

• Can the numbers of an array be made equal?

• Missing elements of a range

• Symmetric pairs in an array

• Maximum product subarray in a given array