python - 创建一个递归函数，获取整数列表中所有可能子集的总和

Question

如果我要获得列表 [1,2,3] 中所有可能的子集组合的总和，我将使用下面的代码:

def f():
    for i in range(2):
        for j in range(2):
            for k in range(2):
                    x = i*1 + j*2 + k*3 
                    print x
f()

我怎样才能创建一个递归函数来对任何列表执行此操作？我可以使用 itertools.combinations 解决这个问题，但我想学习递归方式。谢谢

Answer 1

让我们编写一个递归函数来输出列表所有子集的所有组合。

对于给定列表，组合是列表本身，加上列表的所有组合减去每个成员。这很容易直接转换为 Python:

def combinations(seq):
    yield seq
    for i in range(len(seq)):
        for combination in combinations(seq[:i] + seq[i+1:]):
            yield combination

但是，这显然会产生重复。例如，列表 [1, 2, 3] 包含 [1, 2] 和 [1, 3]，并且它们都包含[1]。那么，如何消除这些重复项呢？简单，只需告诉每个子列表要跳过多少个元素即可:

def combinations(seq, toskip=0):
    yield seq
    for i in range(toskip, len(seq)):
        for combination in combinations(seq[:i] + seq[i+1:], i):
            yield combination

<小时/>

现在，您想对所有组合求和吗？这很简单:

>>> a = [1, 2, 3]
>>> map(sum, combinations(a))
[6, 5, 3, 0, 2, 4, 1, 3]