# 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)

### 1. 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.

Output:

Triplet Exists

## Java

Output:

Triplet Exists

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

### 2. O(n2) solution using Hashing –

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.

Output:

Triplet Exists

## Java

Output:

Triplet Exists

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

### 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).

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).

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 🙂

Get great deals at Amazon

Subscribe
Notify of
Guest
AllergicToBitches

Knapsack method is awesome.. thanks for this.

Guest
Michal

Space complexity for first (with hashing) O(n2) solution is O(n) not O(1). O(1) is the last one.

Guest
foobar

It feels like sort is not needed for the second solution. Isn’t it?