Upper limit: There is a logical maximum that it could be.
You can have 0, 1, 2, 3 quarters, 0, 1, 2 dimes, 0, 1 nickels, and 0, 1, 2 pennies.
This is a total of 4*3*2*3 = 72. Of course, not all of these are distinct; this
is why the answer is smaller. Also, this problem isn't counting $0.00 as a
valid combination. Now that we have an idea of how the problems works, lets
simplify it a little.
Pennies. Since you can have 0, 1, 2 pennies, there will be
NO conflicts. (It takes 5 pennies to cause a problem, since then it will
conflict with the nickel). It means that for all combinations of quarters,
nickels, and dimes, we can have 0, 1, or 2 pennies. This means we can handle
the other three coins and handle the pennies later. This brings the upper limit
down to 24.
One combination has no nickels and no dimes, and another,
equivalent combination has one fewer quarters, one nickel, and two dimes. There
are three ways for the first combination: 1, 2, 3 quarters only. It will bring
down the total to 21.
The pennies we have 21*3=63 possibilities.
General process:
Simplify the problem. (Pennies didn’t cause any conflict so
they just make 3 times as many combination)
Determine the maximum possible combinations. This is a few
multiplications. Not very difficult
Count the duplicates. This is often simpler because there
are usually not that many of them. In this case, just three.
Put it back together.
<span>Of course, sometimes there will be so many conflicts that
anything short of listing them is unreasonable. This was quite a bit more
difficult that it would have been to just list those 62 possibilities. </span>
