python - Niave メソッドを使用した Coin Change Prob の実装

Question

私はそれを述べているコイン変更問題を実装しようとしています

硬貨両替問題は、N セントの両替をしたい場合、値 N が与えられ、S = {S1, S2, . . . , Sm} の価値のある硬貨の場合、変更できる方法はいくつありますか? コインの順番は問いません。貪欲な方法で N セントを変更するすべての可能な方法を特定します。たとえば、N = 4 で S = {1, 2, 3} の場合、{1, 1, 1, 1}、{1, 1, 2}、{2, 2}、{1, 3}。したがって、出力は 4 になるはずです。N = 10 で S = {2, 5, 3, 6} の場合、{2, 2, 2, 2, 2}、{2, 2, 3, 3}、 {2, 2, 6}、{2, 3, 5}、{5, 5}。したがって、出力は 5 になるはずです。

注: これは、最適なソリューション (つまり、コインの最小数) を見つけなければならない元のコイン変更問題ではありません。

以下の Python 実装では、$check$ という名前のリストを使用しています。問題は、プログラムが実行時に同じ $check$ リストを使用しているため、間違った結果が得られることです。関数呼び出しに対してローカルな $check$ リストを使用する必要があります。誰かがこれから抜け出す方法を見つけることができますか..

# N
N = 10

# Set of Changes
s = [2, 3, 5, 6]

lst = []
check = [0, 0, 0, 0]

def Coin_Change_Count(C, check):       
    for k in range(len(s)):        
        i = len(s) - k - 1
        t = C - s[i]

        if (t >= 0):
            if (s[i] == 2):
                check[0] += 1
            elif (s[i] == 3):
                check[1] += 1
            elif (s[i] == 5):
                check[2] += 1
            elif (s[i] == 6):
                check[3] += 1

            if (t >= s[0]):
                Coin_Change_Count(t, check)

            if (t == 0):
                if (not (check in lst)):
                    lst.append(check)

Coin_Change_Count(N, check)
print(len(lst))