CODEWITHSUNDEEP
pythondynamictime-complexitysubsetsubset-sum
Aurelio
Aurelio

Reputation: 115

Subset sum (dynamic programming) in Python - complexity problem

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)

Upvotes: 1

Views: 890

Answers (1)

sam46
sam46

Reputation: 1271

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

Upvotes: 1

Related Questions