Find total number of ways to make change using given set of coins

Question

Given an infinite supply of coins of denominations {20,10,5,1}, find out total number of way to make change of given amount - 'n'?
For example, if given amount is 20, there are 10 ways to make this change as shown below -
(1 of 20),(1 of 10 + 2 of 5),(1 of 10 + 1 of 5 + 5 of 1),(1 of 10 + 10 of 1), (2 of 10), (1 of 5 + 15 of 1),(2 of 5 + 10 of 1),(3 of 5 + 5 of 1),(4 of 5),(20 of 1)

If the amount given is 0 then the total number of ways to make change is 1 - using 0 coins of every given denomination.

Answer 1

Algorithm:
1. consider 20, 10, 5, 1 and take amount as N=20
2. if 20%20==0 then cnt=1
3. if 20%10==0 then cnt=2
4. 20%5==0 => cnt=3 and 20%1==0 => cnt=4
5.20%10!=0 , 20%5!=0, 20%1!=0 so no increment in cnt
6.10%20!=0, 10%5==0 =>cnt=5, 10%1!=0 and similarly for other elements
7. therefore cnt ll be 10 at last.

#include <stdio.h>

int main()
{    
    int a[]={20,10,5,1};
    int n=4;
    int N=20;
    int cnt=0;
    int i,j;

    for(i=0;i<n;i++)
    {
        if(  (N%a[i]) ==0)
            cnt++;
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
            if( (a[i]%a[j])==0)
            {
                cnt++;
                if(i==j) //20%20==0, 10%10==0, 5%5==0, 1%1==0 those ll be included in the above line **cnt++**, so i am decrementing cnt
                    cnt--;
            }
    }

    printf("%d",cnt);
}