与えられた合計に達する数のすべての組み合わせを見つける

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といくつかのパフォーマンス上の問題があります。