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
```

Difficulty: interview

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) #counts number of possibilties 
    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):
    #
    if money == 0: return 1
    if money < 0: return 0
    if not coins: return 0
    return count_change(money-coins[0], coins) + count_change(money, coins[1:])

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):
    # your implementation here
    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)])