Append or copy first in python

Question

I am following a dynamic programming course of return a list of number if you can sum up to a target and running into this problem.

Here is my first try:

def howSum(target, arr, memo={}):
    if target in memo: return memo[target]
    if target == 0: return []
    if target < 0 : return None

    shortest = None

    for i in arr:
        remainderCombination = howSum(target-i, arr, memo)
        if remainderCombination is not None:
            remainderCombination.append(i)
            combination = remainderCombination.copy()
            
            if (shortest == None or len(shortest) > len(combination)):
                shortest = combination.copy()
    
    memo[target] = shortest
    return shortest


print(howSum(8,[1,2,3,5],{}))

which returns the undesirable result of [5, 1, 1, 1].

On my second try, I did like this:

def howSum(target, arr, memo={}):
    if target in memo: return memo[target]
    if target == 0: return []
    if target < 0 : return None

    shortest = None

    for i in arr:
        remainderCombination = howSum(target-i, arr, memo)
        if remainderCombination is not None:
            combination = remainderCombination.copy()
            combination.append(i)
            
            if (shortest == None or len(shortest) > len(combination)):
                shortest = combination.copy()
    
    memo[target] = shortest
    return shortest


print(howSum(8,[1,2,3,5],{}))

and receive the right result of [5, 3].

So basically I only changed the order of copy() and append() but I do not understand why it resulted in different answer.

Edit So as @matszwecja has commented, this is a generic Python's mutable problem

Ah yes, of course. "Least Astonishment" and the Mutable Default Argument

in first example, you append to `remainderCombination` and then copy it, so both objects have newly appended item. In the 2nd example you copy first, so the item is appended only to copy. — matszwecja, Jul 11 '22 at 12:05
For each loops both "remainderCombination" and "combination" should be renewed and I only need "combination" to work properly from that breakpoint. Thus, both snippets should yield same results but they did not. — R.Squallo, Jul 12 '22 at 02:26
Ah yes, of course. ["Least Astonishment" and the Mutable Default Argument](https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument) - are you sure it works as expected? — matszwecja, Jul 12 '22 at 07:02
Oh, I think this is what I am looking for. Still no clue where exactly is the problem and how to prevent this in the future. Thank you and sorry for not eligible to give you an upvote you deserve. — R.Squallo, Jul 12 '22 at 07:31

score 0 · Answer 1 · answered Jul 11 '22 at 12:08

Maybe because at first you were appending i to remainderCombination and setting combination equal to it

remainderCombination.append(i)
combination = remainderCombination.copy()

And in the next snippet you say you just changed the order but it seems you also applied the append on combination rather than remainderCombination

combination = remainderCombination.copy()
combination.append(i)

Also setting a variable equal to some array and then updating the array causes change only in the array not the copy stored in the other variable.

Yes, I am aware of that. My point is the elements in "combination" should be the same for both snippet but apparently it is not. — R.Squallo, Jul 11 '22 at 21:39

Append or copy first in python

1 Answers1