How many different ways can you make change for an amount, given a list of coins? In this problem, your code will need to efficiently compute the answer.
Task
Write a program that, given
An amount N and types of infinite available coins M
A list of M coins - C={C1,C2,C3,..,CM}
The problem can be formally stated:
Given a value N, if we want to make change for N cents, and we have infinite supply of each of C={C1,C2,…,CM} valued coins, how many ways can we make the change? The order of coins doesn’t matter.
Input : first line is the amount and the second line is the list of distinct coins
Output: Total of combination to get the amount
Input
21
1 2 5 10 20 50 100
Output
44
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | import java.util.Scanner; public class HelloWorld{ public static void main(String []args){ int [] sets = new int[]{1,2,5,10,20,50,100}; int amount = 21; System.out.println(findCount(amount,sets,0)); } public static int findCount(int amount, int coins[], int Index) { if (amount == 0) return 1; else if (amount < 0 || coins.length ==Index) return 0; else { int firstCoin = findCount(amount-coins[Index], coins, Index); int nextCoin = findCount(amount, coins, Index+1); return firstCoin + nextCoin; } } } |
No comments:
Post a Comment