Danny

Posted on

# 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.

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);
}

}

``````