CODEWITHSUNDEEP
pythonrecursionmemoization
Coder123
Coder123

Reputation: 11

dictionary value changes as list changes in the previous recursive call

def bestSum(target, numbers, dict):
    if target in dict:
        return dict[target]
    if target == 0:
        return []
    if target < 0:
        return None

    shortestCombination = None
    for num in numbers:
         resultCombination = bestSum(target - num, numbers, dict)
         if resultCombination is not None:
             resultCombination.append(num)
             if (shortestCombination is None or len(resultCombination) < len(shortestCombination)):
                shortestCombination = resultCombination

    dict[target] = shortestCombination
    return shortestCombination

print(bestSum(8,[4,2,7],{}))

This should print 4,4 but it prints 4,4,2. Without memoization it works fine. When I debugged, I saw that dict is storing [2,2] for a key of 2 when it should only store[2]. I think the value is pointing to the reference of shortestCombination(which in turn points to resultCombination) but it is changing with the next recursive call although I am talking about a different shortestCombination. The change happens in the line resultCombination.append(num)

Upvotes: 1

Views: 51

Answers (1)

Rolv Apneseth
Rolv Apneseth

Reputation: 2118

Not sure if this fixes all cases, but for the specific case you are using, it does:

def bestSum(target, numbers, dict):
    if target in dict:
        return dict[target]
    elif target == 0:
        return []
    elif target < 0:
        return None

    shortestCombination = None
    for num in numbers:
        resultCombination = bestSum(target - num, numbers, dict)
        if resultCombination is not None:
            resultCombination.append(num)
            if shortestCombination is None or len(resultCombination) < len(
                shortestCombination
            ):
                shortestCombination = resultCombination[:]  # Difference is here

    dict[target] = shortestCombination
    return shortestCombination

The only change I made was to the line: shortestCombination = resultCombination. I changed it to shortestCombination = resultCombination[:], which sets it to a copy of the list that variable points to, which is probably what you want.

Edit

I'll be honest, I'm not great at recursion. However, let me know if this fixes the problem.

Either sort the numbers array before passing it into the function (more efficient but doesn't look great):

print(bestSum(16, sorted([1, 4, 8], reverse=True), {}))

OR

Sort numbers within the function. This probably leads to a lot of overhead though so I wouldn't recommend it:

for num in sorted(numbers, reverse=True):

The sorting with reverse=True means that the bigger numbers come first, which seems to solve the issue (from my limited testing).

Upvotes: 1

Related Questions