找到所有和为给定数字的子集
我正在学习Python，遇到了一个看起来很简单的问题。
我想找出所有可能的数字组合，使它们加起来等于一个给定的数字。
比如说：4 的组合有 [1,1,1,1]、[1,1,2]、[2,2] 和 [1,3]。
我选择了一种方法，这种方法会生成所有可能的子集（2的n次方），然后只保留那些加起来等于目标数字的组合。不过，我在条件判断上遇到了问题。代码如下：
def allSum(number):
#mask = [0] * number
for i in xrange(2**number):
subSet = []
for j in xrange(number):
#if :
subSet.append(j)
if sum(subSet) == number:
yield subSet
for i in allSum(4):
print i
顺便问一下，这种方法好吗？
4 个回答
1
这里有一种不同的方法，它通过先列出所有的1，然后递归地把后面的元素加进来，从而把这些1合并起来。这样做应该比生成所有可能的子集更有效率：
def allSum(number):
def _collapse(lst):
yield lst
while len(lst) > 1:
lst = lst[:-2] + [lst[-2] + lst[-1]]
for prefix in _collapse(lst[:-1]):
if not prefix or prefix[-1] <= lst[-1]:
yield prefix + [lst[-1]]
return list(_collapse([1] * number))
>>> allSum(4)
[[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]]
>>> allSum(5)
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [1, 1, 3], [2, 3], [1, 4], [5]]
如果你不想要那个简单的情况，可以把最后一个值去掉。如果你只是想遍历结果，可以去掉list的调用，直接返回生成器。
1
这个解决方案不行，对吧？它永远不会把一个数字添加到子集里超过一次，所以你永远得不到像[1,1,2]这样的结果。而且它也不会跳过任何数字，所以你也得不到像[1,3]这样的结果。
所以你这个解决方案的问题有两个方面：第一，你并没有真正生成从1到数字范围内的所有可能子集。第二，所有子集的集合会排除一些你应该包含的东西，因为它不允许一个数字出现超过一次。
这种问题可以被看作是一个搜索问题。想象一下，你想尝试的数字就像树上的节点，然后你可以用深度优先搜索的方法找到所有代表解决方案的路径。虽然这是一棵无限大的树，但幸运的是，你不需要搜索它的全部。
5
这里有一些我几年前看到的代码，可以解决这个问题：
>>> def partitions(n):
if n:
for subpart in partitions(n-1):
yield [1] + subpart
if subpart and (len(subpart) < 2 or subpart[1] > subpart[0]):
yield [subpart[0] + 1] + subpart[1:]
else:
yield []
>>> print list(partitions(4))
[[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]]
额外的参考资料：