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

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