Given a list of change denominations and a target amount of money, calculate the number of ways to make that amount of change.

calculate_change.py

"""
Given a list of change denominations and a target amount of money, 
calculate the number of ways to make that amount of change.
"""

def calculate_variations(total, denomination):
    """
    return all possible sequences of denomination whose sum is <= desired_sum
    """
    list = []

    num_possibilities = int(total / denomination)

    for i in range(1, num_possibilities + 1):
        list.append([denomination] * i)

    return list


denominations = [1, 5, 10, 25]
final_amount = 20

possible_sequences = []
definite_sequences = []

for denomination in denominations:
    new_possible_sequences = []
    for possible_sequence in possible_sequences:
        new_total = final_amount - sum(possible_sequence)
        for result in calculate_variations(new_total, denomination):
            new_sequence = result + possible_sequence
            new_sequence_sum = sum(new_sequence)
            if new_sequence_sum == final_amount:
                definite_sequences.append(new_sequence)
            else:
                new_possible_sequences.append(new_sequence)
    possible_sequences = possible_sequences + new_possible_sequences

    for result in calculate_variations(final_amount, denomination):
        result_sum = sum(result)
        if result_sum == final_amount:
            definite_sequences.append(result)
        else:
            possible_sequences.append(result)

for definite_sequence in definite_sequences:
    print str(definite_sequence)