Why the list is appending unrelated elements?

singam suresh 0
Viewed 58

I am working on this code challenge:

Write a function bestSum(targetSum, numbers) that takes in a targetSum and an array of numbers as arguments.

The function should return an array containing the shortest combination of numbers that add up to exactly the targetSum.

If there is a tie for the shortest combination, you may return any one of the shortest.

This is my code:

def bestsum(targetsum,numbers,memo=None):
    if memo is None:
        memo={}
    if targetsum in memo:
        return memo[targetsum]
    if targetsum==0:
        return []
    if targetsum<0:
        return None

    shortcombo=None
    
    for num in numbers:
        remainder=targetsum-num
        remaindercombo=bestsum(remainder,numbers,memo)
        
        if remaindercombo != None: #current comnination
            
            remaindercombo.append(num)
            
            if(shortcombo is None or len(remaindercombo)<len(shortcombo)):
                shortcombo=remaindercombo
    memo[targetsum]=shortcombo 
    return shortcombo

print(bestsum(7,[5,3,4,7]))
print(bestsum(8,[2,3,5]))
print(bestsum(8,[1,4,5]))
print(bestsum(100,[1,2,5,25]))

Desired output is:

[7]
[5,3]
[4,4]
[25,25,25,25]

But I got something weird instead:

[7]
[5, 3]
[4, 1, 4]
[25, 1, 1, 2, 1, 2, 1, 2, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25]

How can I solve this?

data-structures recursion dynamic-programming python
1 Answers

The problem in your code is that it mutates lists after they have been stored in memo. Imagine a recursive call is made and that recursive call executes:

memo[targetsum] = shortcombo 
return shortcombo

Then the caller of that recursive call takes that returned list and appends a value to it:

remaindercombo.append(num)

But that is problematic, because memo has a reference to that list, and requires that this list is not changed (because it should total to a certain sum).

The solution is to never mutate a list that is stored in memo. There are several ways to accomplish that. One is to treat lists as immutable and thus avoid the use of append. Replace

remaindercombo.append(num)

with:

remaindercombo = remaindercombo + [num]

This creates a new list and that will make your solution work correctly.

trincot0
Related