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.