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

**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++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <iostream> #include <algorithm> using namespace std; // Function to print all distinct triplets in the array with sum // less than or equal to given number int printAllTriplets(int A[], int n, int sum) { // sort the array in ascending order sort(A, A + n); // check if triplet is formed by A[i] and a pair from // sub-array A[i+1..n) for (int i = 0; i <= n - 3; i++) { // maintain two indexes pointing to end-points of the // sub-array A[i+1..n) int low = i + 1, high = n - 1; // loop till low is less than high while (low < high) { // decrement high is total is more than the remaining sum if (A[i] + A[low] + A[high] > sum) high--; else { // if total is less than or equal to the remaining sum, // print all triplets for (int x = low + 1; x <= high; x++) cout << "(" << A[i] << ", " << A[low] << ", " << A[x] << ")"; low++; // increment low } } } } // main function int main() { int A[] = { 2, 7, 4, 9, 5, 1, 3 }; int sum = 10; int n = sizeof(A) / sizeof(A[0]); printAllTriplets(A, n, sum); return 0; } |

`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(n^{2}) and auxiliary space used by the program is O(1).

**Thanks for reading.**

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 🙂

## Leave a Reply

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.

Disregard the above comment, I misread the code.

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

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

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;