How to print all increasing-index triplets in an array?

Question

Given an array ar of length n, how can I print all triplets (ar[i], ar[j], ar[k]) in better than O(n^3) time where 0<=i<j<=k<n ?

Example Input:

ar[]={5,6,7}

Output:

5 6 6
5 6 7
6 7 7

Answer 1

You can't.

Suppose that the array has n elements. Included in the output is each combination of values from the first third of the array, second third, and third third. That right there is n^3/27 = O(n^3) output.

You cannot produce O(n^3) output with less than O(n^3) work.