Гораздо быстрее, чем принятый ответ и не плохо выглядит. Принимаемый ответ делает много одной и той же работы несколько раз, потому что он вычисляет разделы для более низких целых чисел несколько раз. Например, когда n = 22, разница составляет 12,7 секунды против 0,0467 секунд.
def partitions_dp(n):
partitions_of = []
partitions_of.append([()])
partitions_of.append([(1,)])
for num in range(2, n+1):
ptitions = set()
for i in range(num):
for partition in partitions_of[i]:
ptitions.add(tuple(sorted((num - i, ) + partition)))
partitions_of.append(list(ptitions))
return partitions_of[n]
Код по существу тот же, за исключением того, что мы сохраняем разделы меньших целых чисел, поэтому нам не нужно их снова вычислять и снова.