coinchange.cpp

#include <bits/stdc++.h>
using namespace std;
 
// Returns the count of ways we can
// sum S[0...m-1] coins to get sum n
int count(int S[], int m, int n)
{
     
    // If n is 0 then there is 1 solution
    // (do not include any coin)
    if (n == 0)
        return 1;
     
    // If n is less than 0 then no
    // solution exists
    if (n < 0)
        return 0;
 
    // If there are no coins and n
    // is greater than 0, then no
    // solution exist
    if (m <= 0 && n >= 1)
        return 0;
 
    // count is sum of solutions (i)
    // including S[m-1] (ii) excluding S[m-1]
    return count(S, m - 1, n) +
           count(S, m, n - S[m - 1]);
}
 
int main()
{
    int i, j;
    int arr[] = { 1, 2, 3 };
    int m = sizeof(arr) / sizeof(arr[0]);
     
    cout << " " << count(arr, m, 4);
     
    return 0;
}
//by @satkar2001