# Coin change problem (DP-10)

You are given an unlimited supply of coins of given denominations, you need to find the total number of distinct ways to get a desired change.

Sample Input: Coins = { 1, 3, 5, 7 }, N = 8
Expected Output: 6
Explanation: Change for 8 can be made in the following ways –
{ 1, 7 }, { 3, 5 }, { 1, 1, 3, 3 }, { 1, 1, 1, 5 }, { 1, 1, 1, 1, 1, 3 }, { 1, 1, 1, 1, 1, 1, 1, 1 }

Algorithm:

The problem is similar to 0-1 knapsack problem.

1. We can solve the problem using dynamic programming. We create a 2D array of size (m+1, n+1) where m = number of denominations, n = change value.
2. For initialize 0th column with 1 because there is only 1 way to make a change for 0 that is by not including any coin.
3. For each coin, we have two possibilities –
Either we include current coin in solution and recur with remaining change which is equal to N – coins[i] with same number of coins.
Or We exclude the current coins from solution and recur for remaining number of coins (m-1).
```/* Author => Raunak Jain */
#include <bits/stdc++.h>
using namespace std;

int helper(vector<int> coins, int N){
int n = coins.size();
vector<vector<int>> dp(n+1, vector<int>(N+1, 0));
for(int i=0; i<=n; i++){
dp[i][0]=1;
}
for(int i=1; i<=n; i++){
for(int j=1; j<=N; j++){
if(j<coins[i-1]){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
}
}
}
return dp[n][N];
}

int main(){

vector<int> coins = { 1, 2, 3 };
int N = 4;
cout<<helper(coins, N);
return 0;
}```

Also, check out another popular interview problem Equal Sum Partition.