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

 

Download   Run Code

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.

 

Download   Run Code

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)

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

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

avatar
  Subscribe  
newest oldest most voted
Notify of
Tamara Vasylenko
Guest

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

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

Siddd
Guest

Disregard the above comment, I misread the code.

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

Aditya
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

Claudio
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;