//========================================================================
/// <summary>
/// The default set of change units, in U.S. bills.
/// </summary>
//========================================================================
private static int[] defaultValidChangeUnits = new int[] {
1, 2, 5, 10, 20, 50, 100, 500, 1000, 5000, 10000
};
//========================================================================
/// <summary>
/// Returns valid change combinations using recursion.
/// </summary>
/// <param name="totalToChange">The total we're providing change for.</param>
/// <returns>An array of arrays of change units for unique combinations.</returns>
//========================================================================
public static List<List<int>> ViaRecursion(int totalToChange)
{
return ViaRecursion(totalToChange, defaultValidChangeUnits);
}
//========================================================================
/// <summary>
/// Returns the valid change combinations using recursion. Created to make life easier than calling GetUniqueCombinations directly.
/// </summary>
/// <param name="totalToChange">The total to change.</param>
/// <param name="validChangeUnits">A list of change units. Used to override the default set (bills). Example coins.</param>
/// <returns></returns>
//========================================================================
public static List<List<int>> ViaRecursion(int totalToChange, int[] validChangeUnits)
{
if (validChangeUnits == null || validChangeUnits.Length == 0)
{
throw new ArgumentException("Invalid change units list. Array must contain one or more change units.");
}
List<List<int>> results = new List<List<int>>();
if (totalToChange >= validChangeUnits[0])
{
GetUniqueCombinations(new List<int>(), validChangeUnits, 0, 0, totalToChange, results);
}
return results;
}
//========================================================================
/// <summary>
/// Recursive method to generate the change
/// </summary>
/// <param name="changeUnitsInSet">The list of values used to generate the sum so far.</param>
/// <param name="validChangeUnits">The list of valid change units to use.</param>
/// <param name="highest"></param>
/// <param name="sum">The sum we've attained so far.</param>
/// <param name="goal">The change sum we're trying to obtain.</param>
/// <param name="results"></param>
//========================================================================
private static void GetUniqueCombinations(List<int> changeUnitsInSet, int[] validChangeUnits, int highest, int sum, int goal, List<List<int>> results)
{
if (sum == goal)
{
results.Add(new List<int>(changeUnitsInSet));
return;
}
if (sum > goal)
{
return;
}
foreach (int value in validChangeUnits)
{
// Only walk down the right side of the branch making sure we don't get any duplicates.
if (value >= highest)
{
changeUnitsInSet.Add(value);
GetUniqueCombinations(changeUnitsInSet, validChangeUnits, value, sum + value, goal, results);
changeUnitsInSet.RemoveAt(changeUnitsInSet.Count - 1);
}
}
}
/// <summary>
/// Original version pulled off of http://dotnetperls.com/change.
/// </summary>
static void Change(List<int> coins, List<int> amounts, int highest, int sum, int goal)
{
//
// See if we are done.
//
if (sum == goal)
{
Display(coins, amounts);
return;
}
//
// See if we have too much.
//
if (sum > goal)
{
return;
}
//
// Loop through amounts.
//
foreach (int value in amounts)
{
//
// Only add higher or equal amounts.
//
if (value >= highest)
{
List<int> copy = new List<int>(coins);
copy.Add(value);
Change(copy, amounts, value, sum + value, goal);
}
}
}