Input

sum_possible(2017, [4, 2, 10]) # -> False

Usage of any which causes the solution to hang / take a long time

def sum_possible(amount, numbers, cache = None):
  if cache is None:
    cache = {}
  if amount in cache:
    return cache[amount]
  if amount == 0:
    return True
  if amount < 0:
    return False
  cache[amount] = any([sum_possible(amount - number, numbers, cache) for number in numbers])
  return cache[amount]

Usage of a for loop which solves the solution in a reasonable time

def sum_possible(amount, numbers, cache = None):
  if cache is None:
    cache = {}
  if amount in cache:
    return cache[amount]
  if amount == 0:
    return True
  if amount < 0:
    return False
  
  for number in numbers:
    if sum_possible(amount - number, numbers, cache):
      cache[amount] = True
      return True
  
  cache[amount] = False
  return False

I thought that any would short-circuit? Effectively return Trueing early if it encountered a True?

CodePudding user response：

any() would short-circuit, but you're building a list to pass to any first.

cache[amount] = any([sum_possible(amount - number, numbers, cache) for number in numbers])

The list comprehension is evaluated first - and it's eager:

[sum_possible(amount - number, numbers, cache) for number in numbers]

Replace it with a generator expression - that should work (lazy eval):

cache[amount] = any(sum_possible(amount - number, numbers, cache) for number in numbers)