**Problem**

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.

###### Input

int: amount, int vector: coins[n]

###### Output

an integer representing the number of combinations that make up that amount

###### Constraints

`1 <= coins.length <= 300`

`1 <= coins[i] <= 5000`

`0 <= amount <= 5000`

###### Sample Input

coins = [1,2,5], amount = 5

###### Sample 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

###### Solution

This problem could be solved in polynomial time using Dynamic programming.

###### Dynamic Programming

This problem is similar to Coin Change problem, discussed here.

**Optimal Substructure (Bottom up approach)**

dp[j] represents the number of combinations that make up the amount j Now according to optimal substructure: for i = 0 to coins.size()-1: for j = coins[i] to amount: dp[j] = dp[j] + dp[j-coins[i]]

**Base case & Initialisation**

dp[0] = 1, number of ways to make sum = 0, is 1 (not including any coin) dp[j] = 0, if j > 0

###### Code Implementation

```
int change(int amount, vector<int>& coins) {
int n = (int) coins.size();
int dp[amount+1];
dp[0] = 1;
for(int i=1; i<=amount; i++) {
dp[i] = 0;
}
for(int i=0; i<n; i++) {
for (int j=coins[i]; j<=amount; j++) {
dp[j] += dp[j-coins[i]];
}
}
return dp[amount];
}
```

**Time complexity of the above solution is O(n*amount) (n is the size of coins vector) and auxiliary space required is O(amount).**