Find all triplets in array with sum less than or equal to given sum

Question

This was recently asked to a friend in an interview and we do not know of any solution other than the simple O(n³) one.

Is there some better algorithm?

The question is to find all triplets in an integer array whose sum is less than or equal to given sum S.

Note: I have seen other such problems on SO with performance O(n²log n) but all of them were solving the easier version of this problem like where arr[i] + arr[j] + arr[k] = S or where they were only checking whether one such triplet exists.

My question is to find out all i,j,k in arr[] such that arr[i] + arr[j] + arr[k] <= S

Answer 1

I have an idea, but I'm not sure if it works.

Preprocess (remove elements > S) and sort the array first.

Then, after you picking up arr[i] and arr[j] where i < j, you may binary search S - arr[i] - arr[j] in the remaining array[j+1...n]. Once you binary-searched the index m, the k could lie between j+1 and m.

I think this may reduce the complexity. What do you think?