fork(2) download
copy 
  1. #include <iostream>
  2. #include <unordered_map>
  3. using namespace std;
  4.  
  5. // Function to find the total number of ways to get change of N
  6. // from unlimited supply of coins in set S
  7. int count(int S[], int n, int N, auto &lookup)
  8. {
  9.     // if total is 0, return 1
  10.     if (N == 0)
  11.         return 1;
  12.  
  13.     // return 0 if total become negative
  14.     if (N < 0)
  15.         return 0;
  16.  
  17.     // if sub-problem is seen for the first time, solve it and
  18.     // store its result in a map
  19.     if (lookup.find(N) == lookup.end())
  20.     {
  21. 	    // do for each coin
  22. 	    for (int i = 0; i < n; i++)
  23. 	    {
  24. 	        // recurse to see if total can be reached by including
  25. 	        // current coin S[i]
  26. 	        lookup[N] += count(S, n, N - S[i], lookup);
  27. 	    }
  28.     }
  29.  
  30.     // return solution to current sub-problem
  31.     return lookup[N];
  32. }
  33.  
  34. // Coin Change Problem
  35. int main()
  36. {
  37.     // n coins of given denominations
  38.     int S[] = { 1, 2, 3 };
  39.     int n = sizeof(S) / sizeof(S[0]);
  40.  
  41.     // Total Change required
  42.     int N = 4;
  43.  
  44. 	// create a map to store solutions of subproblems
  45. 	unordered_map<int,int> lookup;
  46.  
  47. 	cout << "Total number of ways to get desired change is "
  48.             << count(S, n, N, lookup);
  49.  
  50.     return 0;
  51. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Total number of ways to get desired change is 7
https://ideone.com/Q3byNO
Coin Change Problem - Find total number of ways to get the denomination of coins
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!