Subset sum (dynamic programming) in Python - complexity problem

Question

I have a problem with some implementation of a function that solves the problem of a subset sum in Python.

We have dynamic programming here, so the complexity should be polynomial.

The problem is that if the size of set grows linearly and the size of the numbers also increases linearly (of course it is not a logarithm of numbers) then the code execution time can grow exponentially.

My guess is that this may be due to a particular implementation. Is it possible to improve it somehow?

Code in Python:

def subsetsum(array,num):

    if num == 0 or num < 1:
        return None
    elif len(array) == 0:
        return None
    else:
        if array[0] == num:
            return [array[0]]
        else:
            with_v = subsetsum(array[1:],(num - array[0])) 
            if with_v:
                return [array[0]] + with_v
            else:
                return subsetsum(array[1:],num)

"We have dynamic programming here, so the complexity should be polynomial." Not necessarily. In particular, SUBSET SUM is an NP-complete problem, so if you do solve this in polynomial time, you are a rich person. — Anthony Labarre
– Anthony Labarre, Commented Feb 10, 2019 at 18:16
"The problem is that if the size of set grows linearly and the size of the numbers also increases linearly (of course it is not a logarithm of numbers) then the code execution time can grow exponentially." — Aurelio
– Aurelio, Commented Feb 10, 2019 at 18:18
This is not log of n (size of numers). If we have small numbers can by used dynamic programming... — Aurelio
– Aurelio, Commented Feb 10, 2019 at 18:19

sam46 · Accepted Answer · 2019-02-10 19:20:14Z

1

You're using slices to pass suffixes of array, this will make a copy which has linear runtime. To avoid that you can pass indices instead. Another advantage is that indices are hashable, so you can cache (or memoize) and avoid recomputing answers:

from functools import lru_cache

def ssum(array, N):
    @lru_cache(maxsize=None)
    def subsetsum(idx, num):
        if num < 1 or idx >= len(array):
            return frozenset()
        if array[idx] == num:
            return frozenset([idx])
        with_v = subsetsum(idx + 1, num - array[idx])
        if with_v:
            return with_v | frozenset([idx])
        else:
            return subsetsum(idx + 1, num)
    return list(array[i] for i in subsetsum(0, N))

>>> ssum([1,1,2], 4)
[1, 1, 2]

Unfortunately, there's still the cost of copying the answer obtained from the suffix

edited Feb 10, 2019 at 19:20

answered Feb 10, 2019 at 18:36

sam46

1,2819 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Aurelio Over a year ago

Thanks! What is the approximate real complexity of this implementation?

sam46 Over a year ago

I would say it's similar to this but multiply by a factor of n on top since we're doing a copy of at most n elements in each call

Collectives™ on Stack Overflow

Subset sum (dynamic programming) in Python - complexity problem

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related