我如何更好地优化程序以划分给定总和？ （Python）

Question

如果您不熟悉分区，建议您访问此页面。它很好地说明了这一点：https://en.m.wikipedia.org/wiki/Partition_(number_theory)

在某些情况下，我要解决的问题涉及分区：我试图返回可能的整数分区数，这些整数加到给定的总和中，没有重复的整数。

这是一个简单的示例：如果输入10，则分区（9,1）和（8,2）将计数，因为每个值都是唯一的，并且分区的总和为10。但是，如果分区是像（5,2,1,1,1，）一样，它不会通过，因为一旦将其分解成唯一的值，它就是（5,2,1，），它不会加到10。

[我编写了一个解决方案，可以用较小的数字完成这项工作，例如10。但是，问题的测试用例为200，需要花费[[非常长时间才能运行。

我知道问题在于，分区本质上是指数的，但是我不认为要想出一种优化我所拥有的代码的方法。

这是我的代码：

def solution(n):
    arr = []
    count = 0
    def partitions(num, I=1):
        yield (num,)
        for i in range(I, num//2 + 1):
            for p in partitions(num-i, i):
                yield (i,) + p

    arr = list(partitions(n))

    for part in arr:
        if sum(sorted(list(set(part)))) ==  n and len(part) > 1:
            count += 1

return count

#input: 10 ---> output: 9
#input: 3 ---> output: 1
#input: 50 ---> output: 3657

如果您不熟悉分区，建议您访问此页面。它很好地解释了这个问题：https://en.m.wikipedia.org/wiki/Partition_(number_theory）在某些情况下，我正在尝试解决的问题...

Answer 1

使用内置的Python记忆工具将整数划分为不同的部分（对于参数200快速运行）。