It seems like the author tried to optimise the recursive solution by using a memo object to store all previous successful combinations which in my mind is unnecessary.
The reason I say this is because once we have successful combination all we need to do is keep popping frames off the call stack and returning an end result.
This can be achieved by running the inclusive branch first and then the non-inclusive with an or statement, this means that if the inclusive branch it True our expression will not evaluate the non-inclusive recursive call.
One might argue that previous unsuccessful attempts could be useful to store in a memo in order to avoid future recursive calls of the same index/sum combination but in order to do that we need to change our code a bit to save unsuccessful attempts rather than successful ones.
Here is my solution that demonstrates that:
def can_partition(nums):
sum_of_nums = sum(nums)
mean = sum_of_nums / 2
if mean != sum_of_nums // 2:
return False
return can_partition_recursive(nums, 0, mean)
def can_partition_recursive(nums, idx, total, memo = {}):
if total == 0:
return True
if total < 0 or idx >= len(nums):
return False
result = False
# Check result in memo and use it instead of computing it
if str(idx) + '_' + str(total) in memo:
result = memo[str(idx) + '_' + str(total)]
elif nums[idx] <= total:
result = can_partition_recursive(nums, idx + 1, total - nums[idx], memo)
# Add the result in the memo
memo[str(idx) + '_' + str(total)] = result
# Using an or statement we optimize the solution by not needing to run the
# expression on the right side if the left value is True
return result or \
can_partition_recursive(nums, idx + 1, total, memo)
def main():
print("Can partition: " + str(can_partition([1, 2, 3, 4])))
print("Can partition: " + str(can_partition([1, 1, 3, 4, 7])))
print("Can partition: " + str(can_partition([2, 3, 4, 6])))
main()