I've had the following assignment: Given a list of n integers, each integer in the list is unique and larger than 0. I am also given a number K - which is an integer larger than 0. List slicing of any kind is not allowed
I need to check whether there is a subset that sums up to K. e.g: for the list [1,4,8], and k=5, I return True, because we have the subset {1,4}.
Now I need to implement this using a recursion: So I did, however I needed to implement memoization:
And I wonder what is the difference between those functions' code: I mean, both seem to implement memoization, however the second should work better but it doesn't. I'd really appreciate some help :)
def subsetsum_mem(L, k):
'''
fill-in your code below here according to the instructions
'''
sum_dict={}
return s_rec_mem(L,0,k,sum_dict)
def s_rec_mem(L, i, k, d):
'''
fill-in your code below here according to the instructions
'''
if(k==0):
return True
elif(k<0 or i==len(L)):
return False
else:
if k not in d:
res_k=s_rec_mem(L,i+1,k-L[i],d) or s_rec_mem(L,i+1,k,d)
d[k]=res_k
return res_k
def subsetsum_mem2(L, k):
'''
fill-in your code below here according to the instructions
'''
sum_dict={}
return s_rec_mem2(L,0,k,sum_dict)
def s_rec_mem2(L, i, k, d):
'''
fill-in your code below here according to the instructions
'''
if(k==0):
return True
elif(k<0 or i==len(L)):
return False
else:
if k not in d:
res_k=s_rec_mem2(L,i+1,k-L[i],d) or s_rec_mem2(L,i+1,k,d)
d[k]=res_k
return res_k
else:
return d[k]
You have two problems with your memoization.
First, you're using just k as the cache key. But the function does different things for different values of i, and you're ignoring i in the cache, so you're going to end up returning the value from L, 9, 1, d for L, 1, 1, d.
Second, only in s_rec_mem, you never return d[k]; if it's present, you just fall off the end and return None (which is falsey).
So, the second one does come closer to working—but it still doesn't actually work.
You could fix it like this:
def s_rec_mem2(L, i, k, d):
'''
fill-in your code below here according to the instructions
'''
if(k==0):
return True
elif(k<0 or i==len(L)):
return False
else:
if (i, k) not in d:
res_k=s_rec_mem2(L,i+1,k-L[i],d) or s_rec_mem2(L,i+1,k,d)
d[i, k]=res_k
return res_k
else:
return d[i, k]
… or by just using lru_cache, either by passing down tuple(L) instead of L (because tuples, unlike lists, can be hashed as keys, and your recursive function doesn't care what kind of sequence it gets), or by making it a local function that sees L via closure instead of getting passed it as a parameter.
Finally, from a quick glance at your code:
s_rec_mem at most twice on each set of arguments (assuming you correctly cache on i, k rather than just k), which means memoization can only provide a 2x constant speedup at best. To get any more than that, you need to rethink your caching or your algorithm.lru_cache on tuple(L), i, k means you're memoizing across all runs until you restart the program (or REPL session)—so the first test may take a long time, but subsequent runs on the same L (even with a different k) could benefit from previous caching.