# Leetcode 518. Coin Change II

[link](https://leetcode.com/problems/coin-change-ii)

---

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

#### Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

#### Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

#### Example 3:

Input: amount = 10, coins = [10]
Output: 1

#### Constraints:

- 1 <= coins.length <= 300
- 1 <= coins[i] <= 5000
- All the values of coins are unique.
- 0 <= amount <= 5000

---

The dfs (depth-first search) function is defined to explore all possible combinations of coins and calculate the total number of valid combinations recursively. It takes two arguments:

i: An index representing the current coin denomination being considered.
a: The current amount of money being built up in the recursive process.
The base case of the recursion checks if the current amount a equals the target amount amount. If they are equal, it returns 1, indicating that a valid combination of coins has been found.

Another base case checks if the current amount a exceeds the target amount amount. If it does, it returns 0 because this combination of coins cannot be used to reach the target amount.

A third base case checks if the index i has reached the end of the list of coin denominations coins. If it has, and the target amount hasn't been reached, it returns 0 because there are no more coin denominations to consider.

It checks if the result for the current combination of i and a has already been calculated and stored in the dp dictionary. If it has, it retrieves and returns the stored result to avoid redundant calculations.

If none of the base cases are met, the code calculates the total number of combinations by recursively calling dfs for two scenarios:

Adding the current coin denomination coins[i] to the current amount a, indicating that the current coin is being used.
Moving to the next coin denomination by incrementing i, indicating that the current coin is not being used.
The results of these two recursive calls are summed up, representing the total number of combinations to reach the target amount starting from the current state.

Finally, the change method is called with initial values of 0 for both i and a, indicating that the recursive process starts from the first coin denomination with an initial amount of 0. It returns the total number of combinations to reach the target amount using the provided coin denominations.

#### Solution 1

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

        def dfs(i, a):
            if a == amount:
                return 1
            if a > amount:
                return 0
            if i == len(coins):
                return 0
            if (i, a) in dp:
                return dp[(i, a)]
            
            dp[(i, a)] = dfs(i, a + coins[i]) + dfs(i + 1, a)
            return dp[(i, a)]

        return dfs(0, 0)

O(T): O(n)
O(S): O(n)