How to count possible combination for coin problem

by

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.

More Related Contents:

  1. Find all available combinations
  2. Generate all combinations from multiple lists
  3. How to generate the power-set of a given List?
  4. why i multiply many number make a mistake when i division?
  5. Random Number Algorithm – Implementation in Java
  6. Graph theory puzzle about connectivity?
  7. Write a program that takes an array/arraylist of integer and finds longest sub array/arraylist whose entries are equal [closed]
  8. How to check if an integer is in a set of given ranges? [closed]
  9. Algorithm to divide a given number in two proportions by one of the component of that number
  10. Java – class, get new array of objects
  11. Permutation of array
  12. What’s the best way to build a string of delimited items in Java?
  13. Take n random elements from a List?
  14. How can a KeyListener detect key combinations (e.g., ALT + 1 + 1)
  15. java indexof(String str) method complexity [duplicate]
  16. A better algorithm to find the next palindrome of a number string
  17. Anagram algorithm in java
  18. Nice Label Algorithm for Charts with minimum ticks
  19. Hash Set and Array List performances
  20. implementing debounce in Java
  21. Is there an efficient algorithm for integer partitioning with restricted number of parts?
  22. sorting integers in order lowest to highest java
  23. How do I get the intersection between two arrays as a new array?
  24. What hashing function does Java use to implement Hashtable class?
  25. How to find the only number in an array that doesn’t occur twice [duplicate]
  26. ‘MergeSort Algorithm’ – What’s the better implementation in JAVA? [closed]
  27. Finding the shortest path nodes with breadth first search
  28. Mergesort in java
  29. Time complexity of System.arraycopy(…)?
  30. StackOverflowError computing factorial of a BigInteger?

Leave a Comment