PROBLEM STATEMENT
Suppose a currency exists that has some number of denominations of coins.
Given N and T, both non-negative integers, how many combinations of N coins
will result in a total value of T?
You are not limited in which denominations you may choose, or how many coins of
a particular denomination you may use to find appropriate combinations.
Write a method to take a list of coin denominations, a desired total value (T),
and a desired number of coins (N), and return the number of distinct coin
combinations made up of exactly N coins, that total T in value.
A distinct combination should not be the same as any other combination, even if
the combination is reordered:
{ 1, 2, 5 }, { 2, 5, 7 } are distinct.
{ 7, 2, 5 }, { 2, 5, 7 } are not distinct.
Class Name: Change
Method Name: getCombos
Parameters: int[], int, int
Returns: int
Method signature: (be sure your method is public)
int getCombos(int[] denominations, int totalValue, int numCoins)
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
*denominations will have between 1 and 6 elements, inclusive.
*the elements of denominations will be between 1 and 100, inclusive.
*the elements of denominations are distinct.
*totalValue is between 1 and 1000, inclusive.
*numCoins is between 1 and 5, inclusive.
Examples:
denominations = { 5, 1, 10 }, totalValue = 20, numCoins = 3.
5 + 10 + 5 is the only combination of three coins that will yield a value of 20.
return 1.
denominations = { 50, 5, 25, 10, 1, 100 }, totalValue = 150, numCoins = 5.
There are two combinations that will yield a value of 150:
1) 25 + 25 + 25 + 25 + 50
2) 5 + 10 + 10 + 25 + 100
return 2.
TEST CASES
{ 10, 20, 30 }, 60, 3 returns 2.
{ 1, 4, 7, 8, 9, 2 }, 15, 4 returns 4.