# Print all Triplets in an array with sum less than or equal to given number

Given an unsorted array of integers, print all triplets in it with sum less than or equal to given number.

For example,

Input:
A = [ 2, 7, 4, 9, 5, 1, 3 ]
sum = 10

Output: Triplets are

(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 2, 7)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)

The idea is to sort the given array in ascending order and for each element arr[i] in the array, we check if triplets can be formed by arr[i] and pairs from sub-array [i+1..n). This is illustrated below in C++:

Output:

(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 2, 7)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)

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

We can also solve this problem using backtracking as shown below. Thanks to Tamara Vasylenko for suggesting this alternative approach.

Output:

(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 2, 7)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)     (2 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest
Tamara Vasylenko

Use Backtracking:
```void findTriplet(std::vector<int> & vect, int sum, int begin, std::vector<int> & comb, std::vector<std::vector<int>> & res) {```

``` if (comb.size() == 3) { res.push_back(comb); return; } ```

``` for (int i = begin; i < vect.size() && vect[i] <= sum; i++) { comb.push_back(vect[i]); findTriplet(vect, sum - vect[i], i + 1, comb, res); comb.pop_back(); } }```

Calling from main
```int sum = 10; std::vector<int> vect{ 2, 7, 4, 9, 5, 1, 3 }; // 1 2 3 4 5 7 9```

``` ```

``` std::sort(vect.begin(), vect.end()); std::vector<int> comb; std::vector<std::vector<int>> res; findTriplet(vect, sum, 0, comb, res);``` Guest

Hello,

I think the for loop used to print the triplets should be this:
```for(int x = high; x > low; x++){ //print the triplet A[i], A[low], A[x]```
That’s because the triplets with sum <= targetSum will always be the ones which are to left of the high value which is calculated via `if(A[i] + A[low] + A[high] < sum` condition.
eg: sorted input array: [1,2,3,4,5,7,9], len = 7, sum = 10
Dry run:
i low high x tripletSum
0 1 6 – 1+2+9 = 12 > 10
0 1 5 – 1+2 +7 = 10 (match found, so now we set x to high and decrement it)
0 1 5 5 1+2 +7 = 10 (print)
0 1 5 4 1+2+5 = 8(print)
0 1 5 3 1+2+4 = 7(print)
0 1 5 2 1+2+3 = 6(print)
0 1 5 1 break here as x is not greater than i. Guest

Disregard the above comment, I misread the code. Guest

I think the complexity must be wrong for a simple reason, if we want to print ALL the triplets then in the worst case it could be all the possible triplets in the array, since printing takes at least one operation there is no way to solve the problem in less than O(n^3). Guest

You may be right when we’re required to print all triplets. But the solution would print a triplet (x, y, z) only if (x <= y <= z). So we need some advanced P&C here to sort out the actual complexity.

Here's a series based on the above relation. Can somebody solve it?

1*(n-2)*(n-1) + 2*(n-3)*(n-2) + 3*(n-4)*(n-3) + … + (n-2)*1*2 Guest

It doesn’t change much, the number of triplets with x<=y<=z is still cubic on n, exactly n*(n-1)*(n-2)/6;