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

this asked friend in interview , not know of solution other simple o(n³) one.

is there better algorithm?

the question find triplets in integer array sum less or equal given sum s.

note: have seen other such problems on performance o(n²log n) of them solving easier version of problem arr[i] + arr[j] + arr[k] = s or checking whether 1 such triplet exists.

my question find out i,j,k in arr[] such arr[i] + arr[j] + arr[k] <= s

from worst-case asymptotic perspective, there no better algorithm since size of output potentially o(n^3).

e.g. let array numbers 1 through n. let s = 3n. clearly, subset of 3 array elements less s , there (n choose 3) = o(n^3) subsets.

there few ways can speed non-worst cases though. example, try sorting array first. should give hints.