Determine the combinations of making change for a given amount

Question

My assignment is to write an algorithm using brute force to determine the number of distinct ways, an related combinations of change for given amount. The change will be produced using the following coins: penny (1 cent), nickel (5 cents), dime (10 cents), and quarter (25 cents).

e.g.

Input: 16 (it means a change of 16 cents)

Output: can be produced in 6 different ways and they are:

16 pennies.
11 pennies, 1 nickel
6 pennies, 1 dime
6 pennies, 2 nickels
1 penny, 3 nickels
1 penny, 1 nickel, 1 dime

My algorithm must produce all possible change combinations for a specified amount of change.

I am at a complete loss as to how to even begin starting an algorithm like this. Any input or insight to get me going would be awesome.

one approach might be to use nested for loops for each denomination and calculate sums in the deepest level to see if it matches the target amount — PeskyGnat, Mar 01 '12 at 14:55
+1 For asking just for assistance, not for the final answer. — Adam Matan, Mar 01 '12 at 15:05
Possible duplicate of [How to find all combinations of coins when given some dollar value](http://stackoverflow.com/questions/1106929/how-to-find-all-combinations-of-coins-when-given-some-dollar-value) — e4c5, Apr 13 '17 at 02:53

score 5 · Accepted Answer · answered Mar 01 '12 at 15:16

Ok. Let me explain one idea for a brute force algorithm. I will use recursion here.

Let's you need a change of c cents. Then consider c as

c = p * PENNY + n * NICKEL + d * DIME + q * QUARTER

or simply,

c = ( p * 1 ) + ( n * 5 ) + ( d * 10 ) + ( q * 25 )

Now you need to go through all the possible values for p, n, d and q that equals the value of c. Using recursion, for each p in [0, maximumPennies] go through each n in [0, maximumNickels]. For each n go through each d in [0, maximumDimes]. For each d go through each q in [0, maximumQuarters].

p in [0, maximumPennies] AND c >= p
  |
  +- n in [0, maximumNickels] AND c >= p + 5n
       |
       +- d in [0, maximumDimes] AND c >= p + 5n + 10d
            |
            +- q in [0, maximumQuarters] AND c >= p + 5n + 10d + 25q

For any equality in these steps you got a solution.

score 3 · Answer 2 · answered Mar 01 '12 at 14:54

You could start thinking about this problem by dividing it into sub-problems solve these and then change the problem and adjust your solution.

In your case you could first try to solve the problem using only pennies (With only one obvious solution of course), then look at nickels and pennies and look at all combinations there and so on. To improve this you can reuse solutions from earlier stages in your algorithm.

Sufian Latif · Answer 3 · 2012-03-03T18:14:50.527

Well, if you want brute force solution, you can start with a very naive recursive approach. But to be efficient, you'll need a dynamic programming approach.

For the recursive approach:

1. find out the number of ways you can make using penny only.
2. do the same using penny and nickel only. (this includes step 1 also)
3. the same using penny, nickel and dime only (including step 2).
4. using all the coins (with all previous steps).

Step 1 is straightforward, only one way to do that.

For step 2, the recursion should be like this:

number of ways to make n cent using penny and nickel = 
    number of ways to make (n - [1 nickel]) using penny and nickel
    + number of ways to make n cent using penny only

Step 3:

number of ways to make n cent using penny, nickel and dime = 
    number of ways to make (n - [1 dime]) using penny, nickel and dime
    + number of ways to make n cent using penny and nickel only

Step 4 is similar.

And one thing to remember: you can make 0 cent in one way (i.e. using zero coins), it's the base case.

score 0 · Answer 4 · answered Mar 01 '12 at 14:54

Try to use recursion on this one. Your function should take two parameters - the maximum value you are allowed to use and the amount remaining to pay(you need the first to avoid repetition). Make the function in such a way: if it is in a trivial case (e.g. 1, 5, 10 and you are allowed to take a penny, nickel, dime respectively) print the trivial solution. Also for each case try to take one coin of all the allowed types(e.g. not greater then the maximum allowed) and continue recursively.

Hope this helps.

score -1 · Answer 5 · edited Jun 04 '16 at 17:15

public class PrintAllCoinCombinations {


    static int findChange(int arr[], int index , int value, String str){

        if(value == 0){
            System.out.println(str);
            return 1;
        }
        if(index<0){
            return 0;
        }
        if(value<0){
            return 0;
        }

        int excl  = findChange(arr,index-1,value,str);

        str += " "+ arr[index];

        int incl = findChange(arr,index,value-arr[index],str);

        return incl + excl;

    }

    public static void main(String [] arg){
        int arr[] = {1,5,10,25};
        String s = "";
        int result = findChange(arr,3,16,s);
        System.out.println(result);
    }
}

Determine the combinations of making change for a given amount

5 Answers5

Linked