子集和帶回溯Python的

Question

所以我想打印出來的初始集合加起來21的所有子集到目前爲止，我只能想出這個

def twentyone(array, num=21): 
    if len(array) == 0: 
     return None 
    else: 
     if array[0] == num: 
      return [array[0]] 
     else: 
      with_v = twentyone(array[1:], (num - array[0])) 
      if with_v: 
       return [array[0]] + with_v 
      else: 
       return twentyone(array[1:], num) 

它確實給瞭解決方案，但只有第一個。我如何改變它，以便它能給我所有可能的子集。我試過做了一些改變，但它只給我嵌套列表。你能幫忙的話，我會很高興。

Answer 1

您可以創建一個遞歸發生器：

def twentyone(array, num=21): 
    if num < 0: 
     return 
    if len(array) == 0: 
     if num == 0: 
      yield [] 
     return 
    for solution in twentyone(array[1:], num): 
     yield solution 
    for solution in twentyone(array[1:], num - array[0]): 
     yield [array[0]] + solution 

例如：

>>> list(twentyone([5, 16, 3, 2])) 
[[16, 3, 2], [5, 16]] 

Answer 2

如果你被允許使用標準Python庫，這裏是一個較短的解決方案：

import itertools 
import operator 


def twentyone(array, num=21): 
    subsets = reduce(operator.add, [list(itertools.combinations(array, r)) for r in range(1, 1 + len(array))]) 
    return [subset for subset in subsets if sum(subset) == num] 


print twentyone([1, 2, 5, 6, 8, 9, 10]) 

結果：

[(2, 9, 10), (5, 6, 10), (1, 2, 8, 10), (1, 5, 6, 9), (2, 5, 6, 8)]