いくつかの方法で、n個の要素の集合からK個の要素を選んで数Xを形成できますか？

Question

あり一つの重要な点である - 要素のセットは、1 2 3 5の場合と - 私たちは 任意の回数が、合計ピックアップ要素は、例えばK.

に等しくなければならない任意の要素を選択することができ（1 + 1 + 2 = 4）であり、これらの3つの要素は2つの1と1の2つであるので、答えは1です。

アルゴリズムが大きく役立ちます。 :)

Answer 1

コインチェンジ問題のDP解決策を考えてみましょう。 通常、長さ（Sum + 1）の配列Aのエントリには、整数 - すべてのセルの値を作る方法の数が含まれています。

単純な変更 - 2D配列A[Sum+1][K]を作成します。したがって、A[M][P]には、Pコインを使用して値Mを作成する方法がいくつか含まれています。