Find a target value in an unsorted array of integers by performing additions of integers

Question

Following is an interview question asked by 'Amazon' to me. I still haven't come up with a optimized solution.

Problem Statement:
Given an unsorted array of integers n. Return 'true' if the addition of any integers from that array matches with the target value else return false.

Note:

   1)'n' could be 1000 or 10,000.
   2) Target value could be 'negative'
   3) It may be addition of any 'k' integers (not only two) , where k<=n.  

Test Condition:

    i/p:- Array A[]= {6,7,3,0,12,-5,-6,100}
    Target =  8
    o/p:- TRUE        
As, 6+7+(-5)=8

If we try to do it linearly or normally it will take O(2^n) time complexity.
So I am looking for any method or algorithm which will optimized this problem more.

Thank you in advance!

Answer 1

The subset-sum problem is a well-known NP-complete problem. Here, I'm going to assume that you are looking for any set of numbers to sum to the target (if you're actually looking for only two numbers, there's a five-line solution using a counting hashtable which runs in O(n) time).

There are two basic approaches. The first is just to test every possible subsequence. As you've already observed, that takes O(2ⁿ) time (exponential), which is intractable if n is 1000.

The second is to keep track of what sums are obtainable from prefixes of the list. This is a very simple approach, and works well if the integers are bounded. By way of example, if the input is n k-bit integers, it has computational complexity O(2^kn²) (pseudopolynomial): the biggest the sums can get is 2^kn, so the table has at most 2^kn² entries. This is a typical dynamic programming approach, where the subproblem is T[s][k] = (A[1..k] has a subsequence summing to s), and the final solution is given by T[target][n].

Here's a solution in Python implementing this:

def subset_sum(A, target):
    T = {0} # T[s][0] = (TRUE iff s == 0)
    for i in A:
        T |= {x + i for x in T}
    return target in T

Examples:

>>> subset_sum([-5,6,7,1,0,12,5,-6,100], 13)
True
>>> subset_sum([95, -120, 22, 14491], 13)
False

---

Bonus: If you're curious, here's a solution to the pair-sum problem. It runs in O(n) time and tells you if the array has two numbers summing to the target.

from collections import Counter
def pair_sum(A, t):
    C = Counter(A)
    for k,v in C.iteritems():
        if t == k+k and v > 1: return True # k is in the array twice
        elif t != k+k and t-k in C: return True
    return False

Examples:

>>> pair_sum([3,3,3,4], 13)
False
>>> pair_sum([3,3,3,10], 13)
True
>>> pair_sum([7,7,2], 14)
True
>>> pair_sum([7,14,2], 14)
False