не получение ожидаемых значений после выполнения рекурсии

avatar
Nikhil S N
1 июля 2021 в 18:12
27
0
0

Я пытаюсь получить список с минимальным количеством значений, который дает целевую сумму. Если значение не найдено, нам нужно вернуть None. Сначала я пытался обойтись без переменной memo, в которой хранятся промежуточные результаты, чтобы уменьшить временную сложность. Я получил список со значениями [4,4], что правильно, но после добавления памятки я получаю список со значениями [4, 1, 4], что неверно. Я новичок в Python. Кто-нибудь может указать на ошибку?

def bestSum(targetSum,numbers,memo={}):
    if targetSum in memo.keys():
        return memo[targetSum]
    if targetSum == 0:
        return []
    if targetSum<0:
        return None
    myShortestCombination = None
    for num in numbers:
        remainder = targetSum - num
        reamainderCombination = bestSum(remainder,numbers,memo)
        if reamainderCombination != None:
            reamainderCombination.append(num)
            combination = reamainderCombination
            if (myShortestCombination == None) or (len(combination) < len(myShortestCombination)):
                myShortestCombination = combination
    memo[targetSum] = myShortestCombination
    return myShortestCombination


print(bestSum(8,[1,4,5],memo={}))
print(bestSum(100,[1,2,5,25],memo={}))
Источник

Ответы (0)