algorithm - 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

From a worst-case asymptotic perspective, there is no better algorithm since the size of the output is potentially O(n³).

e.g. Let the array be the numbers 1 through n. Let S = 3n. Clearly, any subset of three array elements will be less than S and there are (n choose 3) = O(n3) subsets.

There are a few ways you can speed up non-worst cases though. For example, try sorting the array first. That should give you some hints.