programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Different ways to give change for various denominations

Varun Gokulnath
Greenhorn
Posts: 13
Hi,

I am currently preparing for a technical interview. I've been solving questions from the book "Cracking the coding interview". I am currently stuck on one of the problems.
Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.

I know that the question asks for the different combinations of the coins that make up the value = n. But, I wanted to test my understanding of recursion and wrote some code to print all possible combintions in the solution.

When I saw the output I realized my mistake. The algorithm uses the logic that makes it see two quarters as different and two dimes as different and so on.

While brainstorming to fix this issue, I thought of using a Set to remove duplicates but still seems wasteful as I should not even be generating them.

Any pointers on how I could fix this algorithm are greatly appreciated.

Thanks
Varun

Stefan Evans
Bartender
Posts: 1837
10
• 1
There is a fairly simple rule you can apply. You might have to pass more information in your recursive calls though.

The problem with your algorithm as you have pointed out is that
10 + 10 + 5 , 10 + 5 + 10 and 5 + 10 + 10 get reported as three different solutions, when they are really only one - 2x10 + 1x5

My suggestion: Add a variable to your recursive call so you can see the ORDER of the coins added. A String would do well enough.
Print that out with each answer so you can see the order of coins in the solution.

Once you see that output, you should be able to spot a fairly simple rule you can apply that can chop out whole branches of the search tree you would otherwise visit.

.

Varun Gokulnath
Greenhorn
Posts: 13
Stefan,

I used an additional parameter to keep track of the item/coin that I previously used. I am posting the full code below, to help others who want to know how I solved the issue.

This gives the correct 13 combinations below:

25s 1 10s 0 5s 0 1s 0 order 25
25s 0 10s 2 5s 1 1s 0 order 10 10 5
25s 0 10s 2 5s 0 1s 5 order 10 10 1 1 1 1 1
25s 0 10s 1 5s 3 1s 0 order 10 5 5 5
25s 0 10s 1 5s 2 1s 5 order 10 5 5 1 1 1 1 1
25s 0 10s 1 5s 1 1s 10 order 10 5 1 1 1 1 1 1 1 1 1 1
25s 0 10s 1 5s 0 1s 15 order 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
25s 0 10s 0 5s 5 1s 0 order 5 5 5 5 5
25s 0 10s 0 5s 4 1s 5 order 5 5 5 5 1 1 1 1 1
25s 0 10s 0 5s 3 1s 10 order 5 5 5 1 1 1 1 1 1 1 1 1 1
25s 0 10s 0 5s 2 1s 15 order 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
25s 0 10s 0 5s 1 1s 20 order 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
25s 0 10s 0 5s 0 1s 25 order 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Thanks
Varun

 It is sorta covered in the JavaRanch Style Guide.