查找所有達到給定總和的數字組合

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一些性能問題。