Given an array of distinct numbers, how do we count the number of triplets with given sum?

For example let us consider the array {5, 2, 7, 8, 4, 3} and the sum is 14,

There are

(2,5,7)

(2,4,8)

(3,4,7)

There are

**3**triplets with the given sum(2,5,7)

(2,4,8)

(3,4,7)

A brute-force algorithm will take O(n^{3}) time. But this problem can also be solved based on 2 Sum problem. Here is the approach.

- Sort the array first.
- Fix the first element in the triplet, and search for a pair of elements whose sum is (Sum – Fixed element)
- Repeat the above step for all the elements

We are essentially searching for a pair of elements for each fixed element. So the time complexity of this solution would be O(n

^{2}).One variation/follow-up of this problem could be to

*find out the number of triplets with sum less than or equal to the given value*.Considering the first example again, there are 8 triplets with sum less than or equal to 14.

2 3 4

2 3 5

2 3 7

2 3 8

2 4 5

2 4 7

3 4 5

3 4 7

2 3 5

2 3 7

2 3 8

2 4 5

2 4 7

3 4 5

3 4 7

The solution for this is similar to the first problem and uses the trick discussed in my previous post.

The code for both is given in the following Java program.