创建一个递归函数，计算整数列表中所有可能子集的和

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]

Answer 2

在编程中，有时候我们需要把一些数据从一个地方转移到另一个地方。这就像把水从一个杯子倒到另一个杯子一样。这个过程可能会涉及到不同的步骤，比如先把水倒到一个小碗里，然后再倒到另一个杯子里。

在代码中，我们也会用到类似的概念，比如把一个变量的值赋给另一个变量。变量就像是存储数据的盒子，我们可以把一个盒子里的东西拿出来，放到另一个盒子里。

有时候，我们还需要对数据进行一些处理，比如加减乘除，这就像在做数学题一样。我们可以用代码来告诉计算机我们想要做什么，然后计算机会按照我们的指示去执行。

总之，编程就是通过写代码来让计算机完成我们想要的任务，就像给它下达指令一样。

def allsums(a):
  x = a[0]
  if len(a) > 1:
    yy = allsums(a[1:])
    return set(x + y for y in yy).union(yy)
  else:
    return set([0, x])