Skip to content

Instantly share code, notes, and snippets.

@tlang0
Last active July 21, 2019 22:12
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save tlang0/dda6ec2eb4200666f8a7 to your computer and use it in GitHub Desktop.
Save tlang0/dda6ec2eb4200666f8a7 to your computer and use it in GitHub Desktop.
Write a function that counts how many different ways you can make change for an amount of money, given an array of coin denominations. For example, there are 3 ways to give change for 4 if you have coins with denomination 1 and 2: 1+1+1+1, 1+1+2, 2+2.
combinations = []
amount = 12
def count_denoms(denoms, comb):
global combinations
for i in range(len(denoms)):
comb_new = comb + [denoms[i]]
if sum(comb_new) < amount:
count_denoms(denoms[i:], comb_new)
elif sum(comb_new) == amount:
print(comb_new)
combinations.append(comb_new)
if __name__ == "__main__":
count_denoms([2, 5, 1], [])
print("Number of combinations: " + str(len(combinations)))
@MUGABA
Copy link

MUGABA commented Sep 24, 2018

how can i write the same program with three arguments

@uwevanopfern
Copy link

uwevanopfern commented Jan 9, 2019


def count_change(money, coins, ops):
    global combinations
    for i in range(len(coins)):
        _new = ops + [coins[i]]
        if sum(_new) < money:
            count_change(money, coins[i:],_new)
        elif sum(_new) == money:
            print(_new)
            combinations.append(_new)
    
if __name__ == "__main__":
    count_change(4,[2, 1], [])
    print("Number of changes: " + str(len(combinations)))```

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