找出所有和为N的组合的好方法？

Question

有没有简单的方法可以生成一个包含数字（0到9）的列表，长度为6，数字可以重复，并且这些数字的总和等于N，比如说20。举个例子：

004673 -> 4+6+7+3=20
121673 -> 1+2+1+6+7+3=20
...

谢谢

Answer 1

使用 itertools 和排列组合：

>>> from itertools import product
>>> l = []
>>> for digits in product('0123456789', repeat=6):
...     if sum(map(int, digits)) == 20:
...             l.append(digits)
...
>>> len(l)
35127
>>> l[1234]
('0', '1', '9', '0', '5', '5')

看起来比 eumiro 的方法稍微快一点：

>>> stm = """l = []
... for digits in product('0123456789', repeat=6):
...     if sum(map(int, digits)) == 20:
...             l.append(digits)
... """
>>> timeit.timeit(stm, setup="from itertools import product", number=3)
10.368315935134888
>>> timeit.timeit("['{0:06}'.format(i) for i in xrange(1000000) if sum(map(int,str(i))) == 20]", number=3)
14.926225900650024

Answer 2

这个方法比其他提出的解决方案快得多：

def iter_fun(sum, deepness, myString, Total):
    if deepness == 0:
        if sum == Total:
            print myString
    else:    
        for i in xrange(min(10, Total - sum + 1)):
            iter_fun(sum + i,deepness - 1,myString + str(i),Total) 

def fixed_sum_digits(digits, Tot):
    iter_fun(0,digits,"",Tot) 


fixed_sum_digits(6,20)

虽然还有一些空间可以让代码更快，但那样的话代码就会变得很无聊，不好读了！

Answer 3

['{0:06}'.format(i) for i in xrange(1000000) if sum(map(int,str(i))) == 20]

result = []
for a in xrange(10):
    for b in xrange(10):
        for c in xrange(10):
            if a+b+c <= 20:
                for d in xrange(10):
                    if 2 < a+b+c+d <= 20:
                        for e in xrange(10):
                            if 10 < a+b+c+d+e <= 20:
                                f = 20 - (a+b+c+d+e)
                                result.append(''.join(map(str, [a,b,c,d,e,f])))

这个方法可以解决问题，大约需要5秒钟就能返回所有35127个数字。

更新 - 作为额外内容，这里有一个虽然看起来不太好但速度快得多的版本（快了大约40倍）: