algorithm - 使用递归检查数组元素是否是两个较早元素的总和

Question

当我偶然发现这本书时，我正在解决一本书中的练习题:

*描述一个递归算法，该算法将检查数组 A 是否为 integers 包含一个整数 A[i] ，它是两个整数的总和 在 A 中较早出现的，也就是说，

 A[i] = A[j] +A[k] for j,k < i.

*

我已经考虑了几个小时，但一直没能想出一个好的递归算法。

Answer 1

没有任何循环的递归解决方案(伪代码):

bool check (A, i, j, k)
    if (A[j] + A[k] == A[i])
        return true
    else
        if      (k + 1 < j)      return check (A, i, j, k + 1)
        else if (j + 1 < i)      return check (A, i, j + 1, 0)
        else if (i + 1 < A.size) return check (A, i + 1, 1, 0)
        else                     return false

递归函数通过 check(A, 2, 1, 0) 调用。为了突出算法的主要部分，它不检查数组最初是否有两个以上的元素。