coin_change2_with_index.py

from functools import lru_cache

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:

        scoins = sorted(coins, reverse=True)
        @lru_cache
        def dfs(amt, index): 
            if amt == 0: return 1
            if amt < 0: return 0
            return sum(dfs(amt - scoins[i], i) for i in range(index+1))
        
        return dfs(amount, len(coins)-1)