查找所有达到给定总和的数字组合

Question

给出一个数字n。使用递归编写一个程序，它找出总和等于n的所有可能的数字组合。例如X1 + X2 + X3 + X4 + X5 + ... +等= N，其中x1> = X2> X3 => = X4> =等等

Example input: 
5 
Example output: 
5=5 
5=4+1 
5=3+2 
5=3+1+1 
5=2+2+1 
5=2+1+1+1 
5=1+1+1+1+1 

Answer 1

下面是潜在的解决这个问题的一种方式。虽然它的效率非常低（数值远高于10），也不依赖于递归，所以你应该把它当作一个参考，你可以开发一个更好的解决方案。

import itertools 


def generate_sum_sequences(n): 
    smaller_values = list(range(1, n+1)) 

    def get_all_combinations(): 
     for i in smaller_values: 
      yield from itertools.combinations_with_replacement(reversed(smaller_values), i) 

    for c in get_all_combinations(): 
     if sum(c) == n: 
      yield c 

if __name__ == '__main__': 
    n = 5 
    for sum_sequence in generate_sum_sequences(n): 
     print('{}={}'.format(n, '+'.join([str(x) for x in sum_sequence]))) 

输出

5=5 
5=4+1 
5=3+2 
5=3+1+1 
5=2+2+1 
5=2+1+1+1 
5=1+1+1+1+1 

Answer 2

def gen_combinations(n, limit=-1): 
    if n < 1: 
     yield [] 
     return 
    if n == 1: 
     yield [1] 
     return 

    if limit == -1: 
     limit = n 

    for first in range(min(limit, n), 0, -1): 
     for seq in gen_combinations(n - first, first): 
      yield [first] + seq 


def main(): 
    n = 40 
    for seq in gen_combinations(n): 
     print("%d=%s" % (n, "+".join(map(str, seq)))) 

这应该工作，但也有处理数字> 50一些性能问题。