Find Triplet with given sum in an array

Given an unsorted array of integers, find a triplet with given sum in it.

 

The problem is a standard variation of 3SUM problem where instead of looking for numbers whose sum is 0, we look for numbers whose sum is any constant C.

For example,


Input:
arr = [ 2, 7, 4, 0, 9, 5, 1, 3 ]
sum = 6

Output: Triplet exists.

Below are triplets with given sum 6
(0 1 5), (0 2 4), (1 2 3)

 


 

Naive Recursive Approach –

 

The idea is similar to 0-1 Knapsack problem and uses recursion to solve this problem. For each item, we either consider current item or exclude it and recurse for remaining elements. We return true if we get desired sum by including or excluding current item.

 
C++ implementation –
 

Download   Run Code

Output:

Triplet Exists

 
We can also use three nested loops and consider every triplet in given array to check if desired sum is found.
 


 

O(n2) solution using Sorting –

 

The idea is to insert each element of the array in a map. Then we consider all pairs present in the array and check if remaining sum exists in the map or not. If remaining sum is seen before and triplet don’t overlap with each other i.e.((i, j, i) or (i, j, j)), we print the triplet and return.

 
C++ implementation –
 

Download   Run Code

Output:

Triplet Exists

 
The time complexity of above solution is O(n2) and auxiliary space used by the program is O(1).

 


 

How to print all distinct triplets?

 

The idea is to sort the given array in ascending order and for each element arr[i] in the array, we check if triplet is formed by arr[i] and a pair from sub-array arr[i+1..n).

 
C++ implementation –
 

Download   Run Code

Output:

(0 1 5)
(0 2 4)
(1 2 3)

 
The time complexity of above solution is O(n2) and auxiliary space used by the program is O(1).

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
AllergicToBitches
Guest
AllergicToBitches

Knapsack method is awesome.. thanks for this.

wpDiscuz