Subset sum algorithms, their time complexity 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 &lt; sum(filter(lambda x: x &lt; 0, xs)):
        return False
    if n &gt; sum(filter(lambda x: x &gt;= 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 &gt; 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 &gt;= 0 and n &gt;= 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
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).