coin change

gistfile1.txt

#! /usr/bin/python

import sys

denominations = [1, 2,3]

def find_all_denom(value, denom, current_denom):

    if value < 0:
        return

    if value == 0:
        print current_denom


    for de in denom:
        
        find_all_denom(value - de, denominations,current_denom + str(de) )
    


d = {}
def find_optimal_solution(value, denom):
    if value in denom:
        return 1
    if value < 0:
        return sys.maxint;
    
    else:
        for d in denom:
            change = []
            change.append(find_optimal_solution(value - d, denom))

        return 1 + min(change)