Verbose project Euler 31 solution (with recursive call to self and cache)

pe031.py

# Project Euler 31 solution
# https://projecteuler.net/problem=31

from functools import lru_cache

@lru_cache(maxsize=1000) # Cache the results (this can be commented out and the function just works slower)
def ways(target, coins):
    
    # Early escape for simple cases
    if target==0: return 1 # This will be the case when reduced_target is 0
    if len(coins)==0: return 0
    if all(target<c for c in coins): return 0

    # Actually do the computation
    total = 0 # Initialize total to 0
    reduced_coins = set(coins) # Mutable set copy of coins
    for coin in coins: # For each coin value
        reduced_coins.remove(coin) # Remove coin from the reduced set
        for j in range(target//coin): # However many times can this coin fit in target (e.g 10 fits 3 times in 33)
            reduced_target = target-(j+1)*coin # Target minus integer multiple of coin value
            # Recursively call self to figure out how many ways are there to reduce the remainder
            remainder_total = ways(reduced_target,frozenset(reduced_coins))
            total += remainder_total
    return total

if __name__ == '__main__':
  # Frozenset is immutable and therefore hashable. This is needed for the lru_cache
  # The use of sets ensures the elements are unique
  coins = frozenset((200,100,50,20,10,5,2,1)) # British coins
  amount = 200 # £2
  print(ways(amount,coins))