How to count possible combination for coin problem

Question

I am trying to implement a coin problem, Problem specification is like this

Create a function to count all possible combination of coins which can be used for given amount.

All possible combinations for given amount=15, coin types=1 6 7  1) 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 2) 1,1,1,1,1,1,1,1,1,6, 3) 1,1,1,1,1,1,1,1,7, 4) 1,1,1,6,6, 5) 1,1,6,7, 6) 1,7,7, 

function prototype:

int findCombinationsCount(int amount, int coins[]) 

assume that coin array is sorted. for above example this function should return 6.

Anyone guide me how to implement this??

Answer 1

Use recursion.

int findCombinationsCount(int amount, int coins[]) {     return findCombinationsCount(amount, coins, 0); }  int findCombinationsCount(int amount, int coins[], int checkFromIndex) {     if (amount == 0)         return 1;     else if (amount < 0 || coins.length == checkFromIndex)         return 0;     else {         int withFirstCoin = findCombinationsCount(amount-coins[checkFromIndex], coins, checkFromIndex);         int withoutFirstCoin = findCombinationsCount(amount, coins, checkFromIndex+1);         return withFirstCoin + withoutFirstCoin;     } } 

You should check this implementation though. I don't have a Java IDE here, and I'm a little rusty, so it may have some errors.