# -*- coding: utf-8 -*- import timeit ncache = 0 cache = {} def partition(number): global cache, ncache answer = {(number,), } if number in cache: ncache += 1 return cache[number] if number == 1: cache[number] = answer return answer for x in range(1, number): for y in partition(number - x): answer.add(tuple(sorted((x, ) + y))) cache[number] = answer return answer print('To 5:') for r in sorted(partition(5))[::-1]: print('\t' + ' + '.join(str(i) for i in r)) print( 'Time: {}\nCache used:{}'.format( timeit.timeit( "print('To 30: {} possibilities'.format(len(partition(30))))", setup="from __main__ import partition", number=1 ), ncache ) )
или https://gist.github.com/sxslex/dd15b13b28c40e695f1e227a200d1646