# Optimisation using memo is unnecessary

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()
``````
1 Like

@Demos

Yes, your approach seems correct. Always there are multiple ways to tackle a problem and the one you choose is also correct.