educative.io

Educative

I don't think we need subset information for memoization

Since we need to store the results for every subset and for every possible sum, we use a two-dimensional list as a lookup table to store the results of the solved subproblems.

We don’t need the track the index array so the answer can be below for memorization.’ Please let me know if I am wrong.

def can_partition(set):
“”"
Checks if two sub-lists has equal sum or not
:param set: Integer list having positive numbers only
:return: returns True if two sub-lists have equal sum, otherwise False
“”"
total = sum(set)
if total % 2!=0:
return False
lookup = [-1 for i in range(total//2+1)]

return can_partition_rec(lookup,set,total//2,0)
# Write your code here!

def can_partition_rec(lookup,set,total,index):
if total == 0:
return True
elif index >= len(set):
return False
if lookup[total] == -1:
if set[index] <= total:
if can_partition_rec(lookup,set,total-set[index],index+1):
lookup[total] = True
return True
lookup[total] = can_partition_rec(lookup,set,total,index+1)
return lookup[total]

Hello @Caiming_Li

Thank you for the feedback. User feedback is very important for us and helps us to continuously improve our content. There can be multiple ways to approach a problem and kudos to you for thinking outside the box and coming up with an alternate solution! You do not need to track the index array but we need to access it or reference it inside our function. That is only possible when we pass it to the function as a parameter.

Hope this helps.