python - メモ化による部分和

Question

宿題のために、サブセット合計の再帰関数を書きましたが、辞書の正しいキーが見つかりません。常にキーエラーが発生し続けます。解決策を探すのではなく、何が摩耗しているのかを理解するのに役立つ説明だけです:

def subset_sum(s, numbers):
    memo={}
    return subset_sum_memo(s, numbers, 1, memo)

def subset_sum_memo(s, numbers, i, memo):
    key= (len(numbers))
    if key not in memo:
        if s==0:
            memo[key]= True
        elif s<0 or numbers==[]:
            memo[key]= False
        for n in range(len(numbers)):
            if subset_sum_memo(s - numbers[n], numbers[:n] + numbers[n+1:], n, memo):
                memo[key]= True
    return memo[key]

私が得ているエラーは次のとおりです。

if subset_sum_memo(s - numbers[n], numbers[:n] + numbers[n+1:], n, memo): 
File "C:\Users\Yarden\Desktop\Python\302154513_ex11_q1.py", line 17, in subset_sum_memo return memo[key] KeyError: 6

更新 1

これは私の新しいコードです:

def subset_sum(s, numbers):
    memo={}
    return subset_sum_memo(s, numbers, 1, memo)


def subset_sum_memo(s, numbers, i, memo):
    key= (len(numbers))
    if s==0:
        memo[key]= True
    if s<0 or numbers==[]:
        memo[key]= False
    if key not in memo:
        for n in range(len(numbers)):
            if subset_sum_memo(s - numbers[n], numbers[:n] + numbers[n+1:], n, memo):
                memo[key]= True
            else:
                memo[key]=False
    return memo[key]

まだ問題があり、原因がわかりません

Answer 1

elif s<0 or numbers==[]:に 変更elif s<0 or isinstance(numbers,list):

Answer 2

これはあなたのコードです：

if key not in memo:
    if s==0:
        memo[key]= True
    elif s<0 or numbers==[]:
        memo[key]= False
    for n in range(len(numbers)):
        if subset_sum_memo(s - numbers[n], numbers[:n] + numbers[n+1:], n, memo):
            memo[key]= True
return memo[key]

key問題は、入っていないかどうかを確認memoしてブロックに入っていることです。次に、複数の条件がありますが、デフォルトのケースではありません。

すべての条件がfalseの場合、値は に設定されませんmemo[key]。