Получение комбинаций из memoized алгоритма подмножества сумм?

Question

Я работал над основной проблемой суммы подмножества. Учитывая сумму, скажем, 6, и числа [1,2,3,4,5,6]), мне пришлось найти общее количество комбинаций, которые составили s (для s = 6: [1,5], [2,4], [1,2,3]).

Я смог решить эту проблему с помощью грубой силы, не смог найти способ ее мемуаровать, поэтому мой код неработоспособный при достаточно больших значениях n.

Я нашел memoized алгоритм here, который работает достаточно хорошо, но он дает мне только количество комбинаций (так что для s = 6 количество комбинаций будет 3) - не сами комбинации. Можно ли как мемуазировать эту проблему (чтобы я мог запускать ее для очень больших значений s) и могли сами выводить сами комбинации?

Answer 1

Вы можете упростить проблему, используя itertools.combinations() как:

>>> from itertools import combinations 
>>> s = 6 
>>> my_list = range(1, s) 
# Value of 'my_list': 
# [1, 2, 3, 4, 5] 

>>> my_combinations = [combinations(my_list, i) for i in range(2, s)] 
# Value of 'my_combinations' (in actual will be containg <combinations> objects): 
# [[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)], [(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)], [(1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 4, 5), (1, 3, 4, 5), (2, 3, 4, 5)], [(1, 2, 3, 4, 5)]] 

>>> my_required_set = [my_set for my_sublist in my_combinations for my_set in my_sublist if sum(my_set) == s] 
>>> my_required_set 
[(1, 5), (2, 4), (1, 2, 3)]