arrays - 如何打印数组中所有增加索引的三元组？

Question

ar给定一个长度数组，n我怎样才能(ar[i], ar[j], ar[k])比O(n^3)time where更好地打印所有三元组0<=i<j<=k<n？

示例输入：

ar[]={5,6,7}

Output:

5 6 6
5 6 7
6 7 7

Answer 1

你不能。

假设数组有n元素。输出中包含数组的前三分之一、第二个三分之一和第三个三分之一的值的每个组合。那就是n^3/27 = O(n^3)输出。

您不能O(n^3)以少于O(n^3)工作的方式产生输出。