Java Coin Change Problem Using Recursion -- not working

Question

I searched up the code and logic for this and basically copied the code from https://www.youtube.com/watch?v=k4y5Pr0YVhg and https://www.techiedelight.com/coin-change-problem-find-total-number-ways-get-denomination-coins/

But my program is wrong because there are definitely more than 2 ways to make 2 pounds.

public class TwoPounds
{
    private static int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
    private static int amount;
    private static int count;

    public TwoPounds()
    {
        amount = 2;
        count = 0;
    }

    public static void main(String[] args)
    {
        TwoPounds run = new TwoPounds();
        count = run.combos(amount);
        run.printOut();
    }

    public int combos(int amountIn)
    {       
        if (amountIn == 0)
        {
            return 1;
        }

        if (amountIn < 0)
        {
            return 0;
        }

        int combosCount = 0;

        for(int i = 0; i < coins.length; i++)
        {
            System.out.println("amountIn now is " + amountIn);
            combosCount += combos(amountIn - coins[i]);
        }
        return combosCount;
    }

    public void printOut()
    {
        System.out.println("\n\n\n");
        System.out.println("There are " + count + " ways can 2 pounds be made, "
            + "using any number of coins");
        System.out.println("\n\n\n");
    }
 }

Output:

There are 2 ways can 2 pounds be made, using any number of coins

Answer 1

Your coins are in cents (or pence, since I guess you are using GB Pounds), so since you are performing amountIn - coins[i] with them, that means that your amount is cents/pence as well.

So, change your amount to the :

amount = 200;

It is worth taking a moment to consider variable naming, and how that might have helped identify - or even avoid - this problem altogether. The terms "amount" and "amountIn" are ambiguous.

Nothing in the words suggests the units. So, get into the habit of making variable names as specific and unambiguous as possible - and include units where appropriate.

eg, if the variables were called 'amountInPounds', then the error becomes more obvious when writing amountInPounds - coins[i]

Now, before you do update to amount = 200;, be aware that :

1) There will be a LARGE number of results (200 pennies, 198 pennies+2p), that will take some time to iterate through one-penny-at-a-time, plus

2) Your code is currently written to go through EVERY discrete ordered combination - eg, it will be counting :

• 198 "1 cent" + 1 "2 cent"
• 197 "1 cent" + 1 "2 cent" + 1 "1 cent"
• 196 "1 cent" + 1 "2 cent" + 2 "1 cent"
• 195 "1 cent" + 1 "2 cent" + 3 "1 cent" etc

Again, WAY too much execution time. What you want is to not start your for(int i = 0; i < coins.length; i++) from zero each time, but instead add an extra parameter to combos - so something like :

public int combos (int amountIn, int startCoin)
{       

    // blah ... existing code ... blah

    for(int i = startCoin; i < coins.length; i++)
    {
        System.out.println("amountIn now is " + amountIn);
        combosCount += combos(amountIn - coins[i], i);
    }

Finally, as I said before, 200 will result in BIG numbers that will be effectively impossible for you to confirm correctness, so instead start with small amounts that you can check.