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.
- 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.
- 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.
- 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.
3 comments