#+ANKI_DECK: study_deck_02
* TODO 0518. Coin Change II :medium:
:PROPERTIES:
:NEETCODE: [[file:../../roadmap.org::*0518. Coin Change II][0518. Coin Change II]]
:END:

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:*


#+begin_src
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
#+end_src


*Example 2:*


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


*Example 3:*


#+begin_src
Input: amount = 10, coins = [10]
Output: 1
#+end_src


*Constraints:*

 - ~1 <= coins.length <= 300~

 - ~1 <= coins[i] <= 5000~

 - All the values of ~coins~ are *unique*.

 - ~0 <= amount <= 5000~

** TODO Approach
Write your approach here.

** TODO Python
#+begin_src python :lc-problem 518 :lc-lang python3
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
#+end_src

** TODO C++
#+begin_src cpp :lc-problem 518
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        
    }
};
#+end_src