#!/usr/bin/env python
#
# recursion
#
def findbest(origarray, denom):
 current = origarray
 i =1
 while(i < size):
	if(i in denom):
		current[i] = 1
		coinlist[i] = [i]
	else:
		k = 1
		while(k < 1 + (i/2)):
			c = current[k] + current[i-k]
			if(c < current[i]):
				current[i] = c
				coinlist[i] = coinlist[k] + coinlist[i-k]
			k+=1
	print(i, current[i], coinlist[i])
	i+=1
 return current


size = 100
origarray = [0]+[100 for i in range(size)]
coinlist = [[]]+[[] for i in range(size)]

denom=[1,5,10,25,50]

x = findbest(origarray, denom)
