Skip to content

Instantly share code, notes, and snippets.

@mingrui
Last active September 14, 2019 16:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mingrui/4ad61f398f56b646702e290719a42311 to your computer and use it in GitHub Desktop.
Save mingrui/4ad61f398f56b646702e290719a42311 to your computer and use it in GitHub Desktop.
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
@mingrui
Copy link
Author

mingrui commented Sep 14, 2019

python coinChange.py

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment