算法题 - 输出数组中数字两两相加的所有结果，要求时间复杂度o(n)

Question

比如数组{7,5,3,4}，输出12,10,11,8,9,7
时间复杂度o(n)，所以不能用循环嵌套

Answer 1

时间复杂度O(n)绝对不可能，起码O(n^2)
不用循环或者只用一个循环是可以的。

#include "stdio.h"

void foo(int * arr, int n, int acc)
{
    if (acc == n * n) return;
    if (acc / n > acc % n)
        printf("%d ", arr[acc / n] + arr[acc % n]);
    foo(arr, n, acc + 1);
}

int main()
{
    int arr[] = { 7, 5, 3, 4 };
    foo(arr, 4, 0);
    return 0;
}