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]