# Print all triplets with sum less than target in an array

7.16K views
0

Write a function to return the list of all such triplets. How will the time complexity change in this case?

Example 1:

Input: [-1, 0, 2, 3], target=3

Output: [-1, 0, 3], [-1, 0, 2]

Explanation: There are two triplets whose sum is less than the target: [-1, 0, 3], [-1, 0, 2]

Example 2:

Input: [-1, 4, 2, 1, 3], target=5

Output:  [-1, 1, 4], [-1, 1, 3], [-1, 1, 2], [-1, 2, 3]

Explanation: There are four triplets whose sum is less than the target:

[-1, 1, 4], [-1, 1, 3], [-1, 1, 2], [-1, 2, 3]

0

Below is the Javascript code for the above problem.

Please follow this blog (https://www.golibrary.co/count-all-triplets-with-sum-less-than-target-in-a-given-array/) for detailed explanation on how the below code works

function triplet_with_smaller_sum(arr, target) {
arr.sort((a, b) => a - b);
const triplets = [];
for (i = 0; i < arr.length - 2; i++) {
search_pair(arr, target - arr[i], i, triplets);
}
return triplets;
}
function search_pair(arr, target_sum, first, triplets) {
let left = first + 1,
right = arr.length - 1;
while ((left < right)) {
if (arr[left] + arr[right] < target_sum) { // found the triplet
// since arr[right] >= arr[left], therefore, we can replace arr[right] by any number between
// left and right to get a sum less than the target sum
for (i = right; i > left; i--) {
triplets.push([arr[first], arr[left], arr[i]]);
}
left += 1;
} else {
right -= 1; // we need a pair with a smaller sum
}
}
}
console.log(triplet_with_smaller_sum([-1, 0, 2, 3], 3));
console.log(triplet_with_smaller_sum([-1, 4, 2, 1, 3], 5));

0

Same algorithm implemented in C++

using namespace std;
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
class TripletWithSmallerSum {
public:
static vector<vector<int>> searchTriplets(vector<int> &arr, int target) {
sort(arr.begin(), arr.end());
vector<vector<int>> triplets;
for (int i = 0; i < arr.size() - 2; i++) {
searchPair(arr, target - arr[i], i, triplets);
}
return triplets;
}
private:
static void searchPair(vector<int> &arr, int targetSum, int first,
vector<vector<int>> &triplets) {
int left = first + 1, right = arr.size() - 1;
while (left < right) {
if (arr[left] + arr[right] < targetSum) {  // found the triplet
// since arr[right] >= arr[left], therefore, we can replace arr[right] by any number between
// left and right to get a sum less than the target sum
for (int i = right; i > left; i--) {
triplets.push_back({arr[first], arr[left], arr[i]});
}
left++;
} else {
right--;  // we need a pair with a smaller sum
}
}
}
};
int main(int argc, char *argv[]) {
vector<int> vec = {-1, 0, 2, 3};
auto result = TripletWithSmallerSum::searchTriplets(vec, 3);
for (auto vec : result) {
cout << "[";
for (auto num : vec) {
cout << num << " ";
}
cout << "]";
}
cout << endl;
vec = {-1, 4, 2, 1, 3};
result = TripletWithSmallerSum::searchTriplets(vec, 5);
for (auto vec : result) {
cout << "[";
for (auto num : vec) {
cout << num << " ";
}
cout << "]";
}
}

Python

def triplet_with_smaller_sum(arr, target):
arr.sort()
triplets = []
for i in range(len(arr)-2):
search_pair(arr, target - arr[i], i, triplets)
return triplets
def search_pair(arr, target_sum, first, triplets):
left = first + 1
right = len(arr) - 1
while (left < right):
if arr[left] + arr[right] < target_sum:  # found the triplet
# since arr[right] >= arr[left], therefore, we can replace arr[right] by any number between
# left and right to get a sum less than the target sum
for i in range(right, left, -1):
triplets.append([arr[first], arr[left], arr[i]])
left += 1
else:
right -= 1  # we need a pair with a smaller sum
def main():
print(triplet_with_smaller_sum([-1, 0, 2, 3], 3))
print(triplet_with_smaller_sum([-1, 4, 2, 1, 3], 5))
main()

JAVA

import java.util.*;
class TripletWithSmallerSum {
public static List<List<Integer>> searchTriplets(int[] arr, int target) {
Arrays.sort(arr);
List<List<Integer>> triplets = new ArrayList<>();
for (int i = 0; i < arr.length - 2; i++) {
searchPair(arr, target - arr[i], i, triplets);
}
return triplets;
}
private static void searchPair(int[] arr, int targetSum, int first, List<List<Integer>> triplets) {
int left = first + 1, right = arr.length - 1;
while (left < right) {
if (arr[left] + arr[right] < targetSum) { // found the triplet
// since arr[right] >= arr[left], therefore, we can replace arr[right] by any number between
// left and right to get a sum less than the target sum
for (int i = right; i > left; i--)
left++;
} else {
right--; // we need a pair with a smaller sum
}
}
}
public static void main(String[] args) {
System.out.println(TripletWithSmallerSum.searchTriplets(new int[] { -1, 0, 2, 3 }, 3));
System.out.println(TripletWithSmallerSum.searchTriplets(new int[] { -1, 4, 2, 1, 3 }, 5));
}
}