Check if an array element is a sum of two earlier elements using recursion

Question

I was solving practice questions from a book when I stumbled upon this one :

*Describe a recursive algorithm that will check if an array A of integers contains an integer A[i] that is the sum of two integers that appear earlier in A, that is, such that

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

*

I have been thinking about this for a few hours but haven't been able to come up with a good recursive algorithm.

Answer 1

A recursive solution without any loops (pseudocode):

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

The recursive function is called with check(A, 2, 1, 0). To highlight the main part of the algorithm it does not check if the array initially has more than two elements.

Answer 2

Not very efficient but..

search(A, j, k) {
   for (int i = 0; i < A.length; i++) {
      if (A[i] == A[j] + A[k]) {
         return i;
      }
   }
   if (k + 1 == A.length) {
      if (j + 1 < A.length) {
         return search(A, j + 1, 0);
      }
      return -1; // not found
   }
   return search (A, j, k + 1);
}

Start the search with

search(A, 0, 0);

Answer 3

In python. The first function (search is less efficient O(n³)), but it also gives the j and k, the second one is more efficient (O(n²)), but only returns i.

def search(A, i):
    for j in xrange(i):
        for k in xrange(i):
            if A[i] == (A[j] + A[k]):
                return i, j, k

    if i > 0:
        return search(A, i - 1)

def search2(A, i, sums):
    if A[i] in sums:
        return i

    if i == len(A) - 1:
        return None

    for j in range(i + 1):
        sums.add(A[i] + A[j])
    return search2(A, i + 1, sums)

if __name__ == '__main__':
    print search([1, 4, 3], 2)
    print search([1, 3, 4], 2)

    print search2([1, 4, 3], 0, set())
    print search2([1, 3, 4], 0, set())

It will print:

None
(2, 0, 1)
None
2