memoized subset-sum 알고리즘에서 다시 조합을 얻으시겠습니까?

Question

나는 기본적인 부분 집합 합계 문제에 대해 연구 해왔다. 주어진 합계, 6, 그리고 숫자 [1,2,3,4,5,6]), 나는 s = 6에 대해 합계 된 총 조합 수를 찾아야한다고 가정 해 봅시다. [2,4], [1,2,3]).

나는 이것을 무력으로 해결할 수 있었지만 메모를 작성하는 방법을 찾을 수 없었으므로 코드가 충분히 큰 값을 가지면 작동하지 않습니다.

아주 잘 작동하는 memoized 알고리즘 here을 찾았지만 조합 수만을 제공합니다 (따라서 s = 6의 경우 조합 수는 3이됩니다). 조합 자체는 아닙니다. 이 문제를 모두 메모 할 수 있습니까? (매우 큰 값으로 실행할 수 있도록) 및은 조합을 직접 출력 할 수 있습니까?

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)]