Ways can you make change for a $100 dollar bill? (Bounded)

29 Aug 2020 - Hadron DaVinci

Problem

You have three $20 dollar bills, five $10 dollar bills, two $5 dollar bills, and five $1 dollar bills.
How many ways can you make change for a $100 dollar bill?

Discussion

Truths:

This scenario is bounded since the number of each coin available is limited.

Solutions

Method1 (Brute Force using Combinations):

step1: Define Input
Create a list with all of the money you have.
x = 3*[20] + 5*[10] + 2*[5] + 5*[1] 
Define target value.
target_value = 100

Define a set to store unique groups.
valid_combos = set()

step2: Find all possible combinations.
We have to vary the number of bills selected. The smallest number of bills
we can select it is 1 and the most number of bills we can select is the length
of the list.
length_x = len(x)
There will be two loops:
outer loop is for the choosing 1 to length_x items
inner loop is for getting all possible combinations
for i in range(length_x):
  for combo in combinations(x, i):
  # do stuff here with combo

step3: Keep sums equal to target value.
While looping through each possible combination, keep the ones which sum to 100.
combo is converted to a tuple (from a list) since sets can’t store lists
# do stuff here with combo
combo = tuple(combo)
if sum(combo) == target_value:
  valid_combos.add(combo)

step4: Print Number of Valid Combos.
# answer is 5
print(len(valid_combos))

Method2 (Coin Change Mother Function):

In a previous post, I created a function which could be used to solve many coin change problems.
Internally, it uses a double loop along with recursion to create a list of coins that sum to the target value.
You can find more about that post here.

Example

coin_values = [20, 10, 5 1]
quantity = [3, 5, 2, 5]
target_value = 100
SOLUTIONS = []

foo(coin_values, quantity, target_solutions)
number_of_ways = len(SOLUTIONS)

# answer is 5
print(number_of_ways) 