Change

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.