recursive with memoization.. please help

[khen95184]

im trying to find the number of combinations to find a sum with several coins.
my original function works,but i dont know how to put the memoization in/
please help me!
update:
i get a list of coins[1,2,3,5] and a sum (10)
and need to count all the combination possibilities to get to that exact sum with unlimited supply of each coin

def find_changes_mem(n, lst, memo=None):
    ##if memo==None:
      ##  memo={}
    if n < 0:
        return 0
    if n == 0:
        return 1
    if not lst:
        return 0
    
    return find_changes_mem(n - lst[0], lst) + find_changes_mem(n, lst[1:])
find_changes_mem(4,[1,2,5,10])

---

We are not permitted to use loops.....

examples:
>>> find_changes_mem(100,[1,2,5,10])
2156

[j.crater]

Please edit your post so the code is in Python code tags. You can find help here. Also, when you copy code, use ctrl+shift+v to preserve indentation.
Can you tell a bit more about the requirements? Perhaps also with giving an example input and expected result.

[khen95184]

Examples:
>>>find_changes_mem(5,[1,2,5,10]) 4

>>> find_changes_mem(10,[1,2,5,10]) 11

>>> find_changes_mem(20,[1,2,5,10]) 40

[Mekire]

So, you need to create the memo dict as is commented out.
If an (n, lst) pair is found in your dict you return its corresponding entry.
This brings us to the next issue; lists aren't hashable so it would need to be made a tuple.
You need to place each newly calculated entry in the dict before returning.
Then each recursive call needs to also pass along the memo dict.

Take a shot at that and get back to us.

[khen95184]

import timeit
def find_changes_rec(n, lst):
    if n < 0:
        return 0
    if n == 0:
        return 1
    if not lst:
        return 0
    return find_changes_rec(n-lst[0], lst) + find_changes_rec(n, lst[1:])

def find_changes_mem(n, lst, memo=None):
    if memo==None:
        memo={}
    if n==0:
        return 1
    if n<0:
        return 0
    if len(lst)==0:
        return 0
    KeyMemozain=(n,tuple(lst))
    if KeyMemozain in memo:
        return memo[KeyMemozain]
    a=find_changes_mem(n-lst[0], lst, memo)+find_changes_mem(n, lst[1:], memo)
    memo[KeyMemozain]=a
    return a
start_time = timeit.default_timer()
print find_changes_mem(20, [1,2,5,10])
end_time = timeit.default_timer()
print(end_time - start_time)
start_time = timeit.default_timer()
print find_changes_rec(20, [1,2,5,10])
end_time = timeit.default_timer()
print(end_time - start_time)

Mekire you are the best! :)))

[khen95184]

cant find the right spot to put the line to update my dictonary

memo[KeyMemozain]=a

could someone please help me??

[Mekire]

Your previous version seems fine to me.  What is the issue with it?