# Ways to make change using arbitrary currency values

def make_change(curr_amt, denom_list, chg_list):
	# returns a list of the nondeterministic leaves of an n-tree you 
	# form when you make change for some arbitrary amount
	# CAUTION: different permutations of the same set of items cause duplicates

	# base case
	if(curr_amt == 0):
		print("LEAF: {", end='')
		index = 0
		while( index < len(chg_list)-1 ):
			print(chg_list[index], end=',')
			index += 1
		else:
			print(str(chg_list[index])+'}')

		chg_list.sort()
		return [chg_list]

	# recursive case
	else:
		ways = []
		for amount in denom_list:
			if(amount <= curr_amt):
				ways += make_change(curr_amt - amount, denom_list, chg_list + [amount])
	return ways

# MAIN
curr_amt = 20
denom_list = [2,3,7,9]
denom_list.sort(reverse=True)
print("Amount:", curr_amt)
print("Denominations:", denom_list)
ways = make_change(curr_amt, denom_list, [])

print("leaves in nondeterministic tree:", len(ways))

# remove duplicates
solution = []
for way in ways:
	if way not in solution:
		solution += [way]

# show the unique ways
print("\nSOLUTION ({} ways):".format(len(solution)))
for index, item in enumerate(solution):
	print("{}. {}".format(index+1, item))