[Solved]: Subset sum algorithms, their time complexity

Problem Detail: 

The algorithm is in Python. Seems correct to me, ideas how to prove it? And what would be its time complexity?

from bisect import bisect  # Implements the decision version of subset sum. # The subset sum problem: given a set and a number find a subset of the set which sums to the given number. # Inputs: an ordered list of integers xs, and an integer n which is the target sum. def subset_sum(xs, n):     if n < sum(filter(lambda x: x < 0, xs)):         return False     if n > sum(filter(lambda x: x >= 0, xs)):         return False     xs = xs[:]     u = {}     def rec(i, n):         if not (i, n) in u:             u[i, n] = False             k = bisect(sums[:i], n)             while k > 0:                 k -= 1                 u[i, n] = u[i, n] or sums[k] == n                 u[i, n] = u[i, n] or rec(k, n - sums[k])         return u[i, n]         sums = xs     return rec(len(sums), n) 

It has been answered below that the above algorithm is exponential time.

That being so, I have a follow up question: Is the algorithm still exponential time if the rec sub-routine above is changed into the following?

def rec(i, n):     if not (i, n) in u:         u[i, n] = False         k = bisect(sums[:i], n)         k -= 1         if k >= 0 and n >= sums[0]::             u[i, n] = sums[k] == n or rec(k, n - sums[k]) or rec(k, n)     return u[i, n] 

The recurrence $T(i, n) = T(i - 1, n - 1) + log_2(i)$ is what I came up with for worst case running time. Maybe that's far off. But from that it seems it is $|S|log(|S|)$.

New information: I have been able to solve a problem instance involving a set of 8192 integers equal to the range (1, 9, ... 65537) and the target n = 65525 in one and a half minute on my laptop. The resulting list consists of 125 integers. That makes the algorithm (with the above changes applied) sub-exponential, certainly not $2^{|S|}$ . The time taken is for the search version which applies the decision version discussed here $|S|$ times.

Here is a link to the full source code of my test set-up:

http://codepad.org/5s5lkHAm

Asked By : user72935

Answered By : Yuval Filmus

Your algorithm is very similar to exhaustive search. It is basically the following approach:

In order to check whether some subset of $S$ sums to $n$, go over all $i \in S$ and check whether some subset of $S \setminus i$ sums to $n - i$.

The actual algorithm uses memoization and a few other optimizations. Its complexity is exponential in the size of $S$ (probably roughly $2^{|S|}$ in the worst case).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47867