파이썬 주어진 합계를 가진 숫자 목록의 모든 조합 찾기

번호 목록이 있습니다.

numbers = [1, 2, 3, 7, 7, 9, 10]

보시다시피이 목록에 숫자가 두 번 이상 나타날 수 있습니다.

주어진 합계를 가진 이러한 숫자의 모든 조합을 가져와야합니다. 10 .

조합의 항목은 반복 될 수 없지만 숫자 의 각 항목은 고유하게 취급되어야합니다. 즉, 목록에있는 두 개의 7 은 동일한 값을 가진 서로 다른 항목을 나타냅니다.

순서는 중요하지 않으므로 [1, 9] 및 [9, 1] 은 동일한 조합입니다.

조합에 대한 길이 제한은 없습니다. [10] 은 [1, 2, 7] 만큼 유효합니다.

위의 기준을 충족하는 모든 조합의 목록을 만들려면 어떻게해야하나요?

이 예에서는 [[1,2,7], [1,2,7], [1,9], [3,7], [3,7], [10]] < / 코드>

 

해결 방법

 

itertools를 사용하여 가능한 모든 크기의 모든 조합을 반복하고 합계가 10이 아닌 모든 항목을 필터링 할 수 있습니다.

import itertools
numbers = [1, 2, 3, 7, 7, 9, 10]
result = [seq for i in range(len(numbers), 0, -1) for seq in itertools.combinations(numbers, i) if sum(seq) == 10]
print result

결과:

[(1, 2, 7), (1, 2, 7), (1, 9), (3, 7), (3, 7), (10,)]

불행히도 이것은 O (2 ^ N) 복잡성과 비슷하므로 20 개 요소보다 큰 입력 목록에는 적합하지 않습니다.

 

참조 페이지 https://stackoverflow.com/questions/34517540