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.
```
The order of coins does not matter:
```
1+1+2 == 2+1+1
```
Also, assume that you have an infinite amount of coins.

Your function should take an amount to change and an array of unique denominations for the coins:

```python
  count_change(4, [1,2]) # => 3
  count_change(10, [5,2,3]) # => 4
  count_change(11, [5,7]) # => 0
```

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Complete search

Ad-hoc

Starter code: def count_change(money, coins):
	

Solutions:
def count_change(money, coins):
	if money < 0:
		return 0
	if money == 0:
		return 1
	if money > 0 and (not coins):
		return 0
	return count_change(money - coins[-1], coins) + count_change(money, coins[:-1])


def count_change(money, coins):
	ways = [1] + [0] * (money + 1)
	for coin in coins:
		for i in range(coin, money + 1):
			ways[i] += ways[i - coin]
	return ways[money]


def count_change(money, coins):
	A = [1] + [0] * money
	for c in coins:
		A = [sum(A[:k + 1][::-c]) for k in range(money + 1)]
	return A[-1]


def count_change(money, coins):
	results = [0] * (money + 1)
	results[0] = 1
	for i in coins:
		for j in range(i, money + 1):
			results[j] += results[j - i]
	return results[money]


def count_change(N, coins):
	count = [0] * (N + 1)
	count[0] = 1
	for i in range(len(coins)):
		j = coins[i]
		while j <= N:
			count[j] += count[j - coins[i]]
			j += 1
	return count[N]


def count_change(money, coins):
	(_, coin, rest) = (coins.sort(reverse=True), coins[0], coins[1:])
	if not rest:
		return int(not money % coin)
	return sum((count_change(money - i, rest) for i in range(0, money + 1, coin)))


def count_change(money, coins):
	if len(coins) == 0 or money < 0:
		return 0
	if money == 0:
		return 1
	return count_change(money - coins[0], coins) + count_change(money, coins[1:])


def count_change(money, coins):
	if len(coins) == 1:
		return 1 if money % coins[0] == 0 else 0
	coins = sorted(coins, reverse=True)
	return sum([count_change(money - i * coins[0], coins[1:]) for i in range(money // coins[0] + 1)])