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

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 int开发者_开发百科egers 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.

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.

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);

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

  /**
   * 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.
   * @param A - array
   * @param i - initial starting index (0)
   * @param j - initival value for j (0)
   * @param k - initial value for k (0)
   * @param n - length of A - 1
   * @return - true if combination of previous 2 elements , false otherwise
   */
  public boolean checkIfPreviousTwo(int[] A, int i, int j, int k, int n){
    if(i >= n) return false;
    if(j < i && k < i){
      if(A[j] + A[k] == A[i]) return true;
      return(
        checkIfPreviousTwo(A, i, j + 1, k, n) ||
        checkIfPreviousTwo(A, i, j, k + 1, n)
      );
    }
    return checkIfPreviousTwo(A, i + 1, j, k, n);
  }

This algorithm should be fairly efficient (well, O(n²)):

import Data.Set (Set, empty, fromList, member, union)

-- Helper function (which does all the work)
hassum' :: (Ord a, Num a) => Set a -> [a] -> [a] -> Bool
-- Parameters:
--   1. All known sums upto the current element
--   2. The already handles elements
--   3. The not yet checked elements

-- If there are no elements left to check, there is no sum 
hassum' _    _    []     = False
-- Otherwise...
hassum' sums done (x:xs)
   -- Check if the next element is a known sum
   | x `member` sums     = True
   -- Otherwise calculate new possible sums and check the remaining elements
   | otherwise           = hassum' sums' done' xs
       where sums' = sums `union` fromList [x+d | d <- done]
             done' = x:done

-- Main function
hassum :: (Ord a, Num a) => [a] -> Bool
hassum as = hassum' empty [] as

I hope you can make sense of it even if you might not know Haskell.

The Java version, it also return the index of i,j,k. the running time of the worst case is O(N^2)

=1= using recursion

    private static void findSum(Object[] nums, long k, int[] ids/* indexes*/) {
    // walk from both sides towards center
    int l = ids[0];
    int r = ids[1];
    if (l == r) {
        ids[0] = -1;
        ids[1] = -1;
        return;
    }
    int sum = (Integer) nums[l] + (Integer) nums[r];
    if (sum == k) {
        return;
    }
    if (sum < k) {
        ids[0]++;
    } else {
        ids[1]--;
    }
    findSum(nums, k, ids);
}

private static int binarySearchPositionIndexOf(List<Integer> list, int l, int r, int k) {
    int m = (l + r) / 2;
    if (m == l) { // end recursion
        return r;
    }

    int mv = list.get(m);
    if (mv == k) {
        return m;
    }
    if (mv < k) {
        return binarySearchPositionIndexOf(list, m, r, k);
    }
    return binarySearchPositionIndexOf(list, l, m, k);
}

private static void check(List<Integer> data, List<Integer> shadow, int i, int[] ids) {
    if (i == data.size()) {
        ids[0] = -1;
        ids[1] = -1;
        return;
    }
    // sort it in
    int indexAfterSort = -1;
    int v = data.get(i);
    if (v >= data.get(i - 1)) {
        indexAfterSort = i;
    } else if (v <= data.get(0)) {
        indexAfterSort = 0;
    } else if (data.size() == 3) {
        indexAfterSort = i - 1;
    } else {
        indexAfterSort = binarySearchPositionIndexOf(data, 0, i - 1, data.get(i));
    }
    if (indexAfterSort != i) {
        data.add(indexAfterSort, data.remove(i));
        shadow.add(indexAfterSort, shadow.remove(i));
    }
    // find sum
    if (indexAfterSort >= 2) {
        List<Integer> next = data.subList(0, indexAfterSort); //[)
        ids[0] = 0;
        ids[1] = next.size() - 1;
        findSum(next.toArray(), data.get(indexAfterSort), ids);
    }
    // recursion
    if (ids[0] == -1 && ids[1] == -1) {
        check(data, shadow, i + 1, ids);
        return;
    }
    ids[0] = shadow.get(ids[0]);
    ids[1] = shadow.get(ids[1]);
    ids[2] = i;
}

public static int[] check(final int[] array) {
    List shadow = new LinkedList() {{
        for (int i = 0; i < array.length; i++) {
            add(i);
        }
    }};

    if (array[0] > array[1]) {
        array[0] ^= array[1];
        array[1] ^= array[0];
        array[0] ^= array[1];

        shadow.add(0, shadow.remove(1));
    }
    int[] resultIndex = new int[3];
    resultIndex[0] = -1;
    resultIndex[1] = -1;
    check(new LinkedList<Integer>() {{
        for (int i = 0; i < array.length; i++) {
            add(array[i]);
        }
    }}, shadow, 2, resultIndex);
    return resultIndex;
}

Test

@Test(timeout = 10L, expected = Test.None.class)
public void test() {
    int[] array = new int[]{4, 10, 15, 2, 7, 1, 20, 25};
    int[] backup = array.clone();
    int[] result =  check(array);
    Assert.assertEquals(backup[result[2]], 25);
    Assert.assertEquals(result[2], 7);

    Assert.assertEquals(backup[result[0]], 10);
    Assert.assertEquals(result[0], 1);

    Assert.assertEquals(backup[result[1]], 15);
    Assert.assertEquals(result[1], 2);

    array = new int[]{4, 10, 15, 2, 7, 1, 10, 125};
    backup = array.clone();
    result =  check(array);

    Assert.assertEquals(result[0], -1);
    Assert.assertEquals(result[1], -1);
}

=2= simple one without recurison:

// running time n + n^2
// O(n^2)
public static int[] check2(final int[] array) {
    int[] r = new int[3];
    r[0] = -1;
    r[1] = -1;
    r[2] = -1;

    Map<Integer, List<Integer>> map = new HashMap(array.length);
    for (int i = 0; i < array.length; i++) {
        int v = array[i];
        List<Integer> ids = map.get(v);
        if (ids == null) {
            ids = new LinkedList();
        }
        ids.add(i);
        map.put(v, ids);
    }

    for (int k = 0; k < array.length; k++) {
        int K = array[k];
        for (int j = 0; j < array.length; j++) {
            int I = K - array[j];
            if (map.keySet().contains(I)) {
                List<Integer> ids = map.get(I);
                for (int i : ids) {
                    if (i != j) {
                        r[0] = j;
                        r[1] = i;
                        r[2] = k;
                        return r;
                    }
                }
            }
        }
    }
    return r;
}

Test:

    int[] array = new int[]{0,8,8};
    int[] result =  check2(array);
    Assert.assertEquals(array[result[2]], 8);
    Assert.assertEquals(result[2], 1);
    Assert.assertEquals(array[result[0]], 0);
    Assert.assertEquals(result[0], 0);
    Assert.assertEquals(array[result[1]], 8);
    Assert.assertEquals(result[1], 1);