0

When playing arround with python memoization, I wrote the following code.

def can_sum_rec(target, nums):
    if target < 0:
        return False
    if target == 0:
        return True
    for i in nums:
        if can_sum_rec(target - i, nums):
            return True
    return False

def can_sum_mem(target, nums, mem={}):
    if target in mem:
        return mem[target]
    if target < 0:
        return False
    if target == 0:
        return True
    for i in nums:
        if can_sum_mem(target - i, nums, mem):
            mem[target] = True
            return True
    mem[target] = False
    return False

However, I am getting some confusing test results.

tests = [(7, [3, 2]), (7, [2, 4]), (7, [5, 4, 7, 3]), (8, [2, 3, 5])]
for target, nums in tests:
    print(can_sum_mem(target, nums))

True True True True

Obviously, 2 and 4 cannot sum to 7. However, when testing the cases separately the results are fine.

tests = [(7, [2, 4])]
for target, nums in tests:
    print(can_sum_mem(target, nums))

False

I can't seem to find any global variable. So I would really appreciate it if someone could point out the issue here.

quamrana
  • 37,849
  • 12
  • 53
  • 71
TIM
  • 85
  • 6
  • 1
    You are only memoizing `target`, not `nums`, so all results for `7` will be the same. Create a tuple of `(target, tuple(nums))` as key instead. It might be easier to use a decorator for memoization, or just use [`functools.cache`](https://docs.python.org/3/library/functools.html#functools.cache). – Jan Christoph Terasa Jan 10 '21 at 11:55
  • Thank you so much, you literally saved me hours. – TIM Jan 10 '21 at 12:18

0 Answers0