子集和（动态编程）在Python - 复杂性问题

Question

我有一种解决Python中的子集和问题的函数的一些执行问题。

我们这里有动态规划，所以复杂性应该是多项式。

问题是，如果设置的大小线性增长和数字的大小也线性增加（当然这不是数字的对数），那么代码执行时间可成倍增长。

我的猜测是，这可能是由于特定的实现。是否有可能以某种方式改进呢？

代码在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)

Answer 1

您使用的切片传递array的后缀，这将使得其具有线性运行时的副本。要避免这种情况，你可以通过指数来代替。另一个优点是，指数是哈希的，所以你可以缓存（或memoize），并重新计算避免答案：

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]

遗憾的是，还是有抄袭答案从后缀获取成本