coinChange.py

coinChange.py

def coinChange(denominations, multiplicities, amounts):
	if not amounts or len(amounts) == 0:
		return True

	if amounts[0] == 0:
		return coinChange(denominations, multiplicities, amounts[1:])

	for j in range(len(amounts)):
		i = len(multiplicities) - 1
		while i >= 0:
			if multiplicities[i] > 0:
				if denominations[i] <= amounts[j]:
					amounts[j] -= denominations[i]
					if amounts[j] > 0:
						multiplicities[i] -= 1
						continue
					if amounts[j] == 0:
						multiplicities[i] -= 1
						return coinChange(denominations, multiplicities, amounts[1:])
					else:
						amounts[j] += denominations[i]
						pass
			i -= 1
		if len(amounts) == 0:
			return True
		else:
			return False

if __name__ == "__main__":
	denominations = [1, 5, 10, 20, 100]
	assert coinChange(denominations, [1, 3, 2, 3, 7], []) == True
	assert coinChange(denominations, [1, 3, 2, 3, 7], [10]) == True
	assert coinChange(denominations, [1, 3, 2, 3, 7], [0]) == True
	assert coinChange(denominations, [1, 3, 2, 3, 7], [0, 0]) == True
	assert coinChange(denominations, [1, 3, 2, 3, 7], [0, 0, 0]) == True
	assert coinChange(denominations, [1, 3, 2, 3, 7], [11]) == True
	assert coinChange(denominations, [1, 3, 2, 3, 7], [12]) == False
	assert coinChange(denominations, [1, 3, 2, 3, 7], [0, 10, 20]) == True
	assert coinChange(denominations, [1, 3, 2, 3, 7], [20, 10, 0]) == True
	assert coinChange(denominations, [1, 3, 2, 3, 7], [12, 10, 0]) == False
	assert coinChange(denominations, [1, 3, 2, 3, 7], [700, 60, 0]) == True
	assert coinChange(denominations, [1, 3, 2, 3, 7], [700, 70, 0]) == True
	assert coinChange(denominations, [1, 3, 2, 3, 7], [700, 60, 35]) == True
	assert coinChange(denominations, [1, 3, 2, 3, 7], [700, 60, 35, 0]) == True
	assert coinChange(denominations, [1, 3, 2, 3, 7], [700, 60, 35, 1]) == True
	assert coinChange(denominations, [1, 3, 2, 3, 7], [700, 60, 35, 1, 0]) == True
	assert coinChange(denominations, [1, 3, 2, 3, 7], [700, 60, 35, 1, 1]) == False
	assert coinChange(denominations, [1, 3, 2, 3, 7], [0, 60, 35, 700]) == True

python coinChange.py