Algorithms Challenge (2) Combination Coin Change - Different coins added up to a given amount

Question :
There are {1, 2 , 5} dollar types coins for selection. Use different combinations of these types coins to adding up to the given amount 50.

Answer:
We can use different types of dynamic programming methods to solve this problem. In this article , we choose to use Dynamic programming - Bottom up method.

The implementation logic is simple like this :

1. Set combinations as an array , its size is "amount +1"
2. combinations[0] = 1 , it means the first combination ways number is 1
3. We can loop the coins into the combinations array. When the amount(the value in the position of the combinations array) is greater than coin , then we can use the formular : combinations[amount] += combinations[amount - coin];

Code:

public class coinsCombinationWays {

    static int getTotalWays(int[] coins, int amount){
         int[] combinations = new int[amount + 1];
         combinations[0] = 1;

         for(int coin: coins) {
            for(int j=1; j<combinations.length; j++){
              if(j>=coin)
               combinations[j] += combinations[j-coin];
           }
         }
        return combinations[amount];
   } 

   public static void main(String[] args) {
       int[] coins = {1, 2, 5};
       int amount= 50; 

       int totalWays += getTotalWays(coins, amount);
       System.out.println(totalWays);
    }

}

Comments

[Danny]

Looks like the Big O complexity is O(n)