0

Hi I was doing some dynamic programing exercises and stubbled upon the Bestsum Problem where you are given a Targetnumber and a array of numbers and you have to find the shortest sum using the number in the array to get the Target number for example given the function bestsum(7,[1,2,4]) it schoud return [4,2,1]

def howsum(targetsum, numbers, memo = {}):
if targetsum in memo:
    return memo[targetsum]

if targetsum == 0:
    return []

if targetsum < 0:
    return None

shortestcombination = None

for n in numbers:
    remainder = targetsum - n
    result = howsum(remainder, numbers, memo)
    if result != None:
        combination = []
        combination = result
        combination.append(n)
        if shortestcombination == None or len(combination) < len(shortestcombination):
            shortestcombination = combination

memo[targetsum] = shortestcombination
return shortestcombination


if __name__ == '__main__':
print(howsum(7, [1, 4, 2]))

Here is my code witch gives the solution right when I comment out memo[targetsum] = shortestcombination and i dont know what went wrong with my memoization so thanks in advance if you can help

Rivow
  • 1
  • 1

1 Answers1

0

I Found The problem and it has to do with how list operation in python works. The issue is in the line "combination.append(n)" append modifies the list in place which is what produces the bug in memo. so the solution is to use the syntax "combination = combination + [n]" so that the code creates a new list and it assigns it to combination and That fixes the bug.

If you want more details here is another thread that explains += operator for list vs = +

Why does += behave unexpectedly on lists?

Rivow
  • 1
  • 1