Recursive Coin Change Making by printing all possible ways

Question

I have tried to print all the paths which give the given amount. But my code does not work properly. I think I am missing some points to print all possible combinations. For example;

• if amount: 7 and startCoin = 25, the program needs to give me: {5,1,1} and {1,1,1,1,1,1,1}.

Can you help me to fix these problem?

Note: Preferably Java Solutions

class Solution {

      static int[] coinSet = {1,5,10,25};
      static List<List<Integer>> possibleWays = new ArrayList<>();
      static List<Integer> currentWay = new ArrayList<>();

      private static int makeChange(int amount, int startCoin){

        boolean flag = false;
        for(int i =0 ; i < coinSet.length ; i++){
          if(coinSet[i] == startCoin) {
            flag =true;
          }
        }

        if(!flag){
          throw new IllegalArgumentException("startCoin has to be in the specified range");
        }

        int nextCoin = 0;
        switch(startCoin) {
          case 25:
            nextCoin = 10;
            break;

          case 10:
            nextCoin = 5;
            break;

          case 5:
            nextCoin = 1;
            break;

          case 1:
            possibleWays.add(currentWay);
            currentWay = new ArrayList<>();
            return 1;
        }

        int ways = 0;

        for(int count = 0; count * startCoin <= amount; count++){
          ways += makeChange(amount - (count * startCoin),nextCoin);
        }

        return ways;

      }    
      public int calculateNumberOfWays(int amount, int startCoin) throws Exception {
        if (amount == 0) {
          throw new Exception();    }

        return makeChange(amount, startCoin);
      }

      public static void main(String[] args) {

        System.out.println(makeChange(5,25));
        System.out.println(possibleWays);

      }
    }

Answer 1

This can be solved using backtracking but that is not very efficient, below is the working java code

/**
 * Created by sumit sharma on 3/1/2016.
 */
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.Random;

public class Main {
    static int[] coinSet = {1,5,10,25};
    static List<List<Integer>> possibleWays = new ArrayList<>();
    static List<Integer> currentWay = new ArrayList<>();
    public static void main(String[] args) {
        List<Integer> countOfCoins = new ArrayList<>();
        makeChange(7, 0, countOfCoins);
        //System.out.print(possibleWays);
    }

    private static int makeChange(int amount, int startCoinIdx, List<Integer> coinsSoFar) {
        if(startCoinIdx == coinSet.length){
            if(amount == 0){
                possibleWays.add(coinsSoFar);
                System.out.println(coinsSoFar);
            }
            //System.out.println(coinsSoFar);
            return 0;
        }
        for(int count = 0;(count*coinSet[startCoinIdx]) <= amount;count++){
            List<Integer> temp = new ArrayList<>();
            for(int i = 0;i < coinsSoFar.size();i++) temp.add(coinsSoFar.get(i));
            for(int i = 0;i < count;i++) temp.add(coinSet[startCoinIdx]);
            makeChange(amount - (count * coinSet[startCoinIdx]),startCoinIdx+1, temp);
            temp.clear();
        }
        return 0;
    }
}

Link to solution on Ideone : http://ideone.com/kIckmG