n個の要素の配列から要素Kを形成する方法の数を求める

Question

要素の配列がnの場合、これらの要素から要素Kが形成される方法の数を求める。 配列が{3,9,1,4,2,5}とK = 5 可能な方法があるされている場合たとえば、：

1+4, 
2+3, 
1+2+2, 
1+1+1+1+1, 
1+3+1, 
1+1+1+2 

だから、答えは6 する必要があり、このためのアルゴリズムを提案してください。

Answer 1

基本的なアルゴリズムは次のようになります。配列の各要素xため

• ：
  • xがkに等しい場合xよりも小さい場合、次いで[x]は溶液
  • ありますkとし、k-xの解を見つけ、x

コードでこれを実現する最も簡単な方法は、単純な再帰アルゴリズム（ここでPythonで）ようになるであろう。これは、より大きな配列のための非常に効率的でないことが

def find_sums(array, k): 
    for x in array: 
     if x == k: 
      yield [x] 
     elif x < k: 
      for s in find_sums(array, k - x): 
       yield [x] + s 

注、 find_sums(array, k - x)への呼び出しは何度も繰り返されますが、これは簡単にmemoizationまたはdynamic programmingとすることができます。また、結果には、[1, 4]および[4, 1]のような「重複」が含まれている可能性があります。 （部分的な結果の中で最大の要素を追跡する）か、後でフィルタリングすることができます（たとえば、ソートしてセットに変換する）。また、結果に特異なリストを必要としない場合は、それらもフィルタリングする必要があります。

これらの調整は、読者の練習として残されています。