Make Changes

Given an infinite number of quarters (25 cents), dimes (10 cents), nickles (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.

Solution: this question is similar to Combination Sum, while is simpler. We do not need to output the combination, but just give the number of ways. Solve it recursively.
Ways = representing n cents by using 0 quarter,
          + representing n cents by using 1 quarter,
          + representing n cents by using 2 quarters
             ...
          + representing n cents by using many quarters

Then for each case, the formula can be expanded as
            representing 100 cents by using 0 dime
          + representing 100 cents by using 1 dime
              ...
          + representing 75 cents by using 0 dime
          + representing 75 cents by using 1 dime

Java语言: Coins

01 public int numOfWays(int sum)
02 {
03     int []coins={25,10,5,1};
04   
05     //start from quarters
06     return numOfWays(sum,coins,0);
07 }
08 
09 public int numOfWays(int sum, int [] coins, int start)
10 {
11 
12     if(sum<0)
13         return 0;
14   
15     //Base case: only pennies are used
16     if(start==coins.length-1)
17     {
18         return 1;
19     }
20   
21     int value=coins[start];
22     int ways=0;
23   
24     //use the coin at coins[start] 0, 1, 2 or many times
25     while(sum>=0)
26     {              
27         ways+=numOfWays(sum,coins,start+1);
28         sum-=value;
29     }
30     return ways;
31 }