educative.io

Educative

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.