https://www.hackerrank.com/challenges/ctci-coin-change/problem

.py

# my solution:

def make_change(coins, n):
    coins = list(coins)
    if 'D' not in make_change.__dict__:
        make_change.D = {}
    id = tuple(coins), n
    if id not in make_change.D:
        coin = coins.pop(0)
        make_change.D[id] = sum(make_change(list(coins), n-i*coin) for i in range(n//coin+1)) if coins else int(n % coin == 0)
    return make_change.D[id]


# adapted from a cool one from forum:

def make_change(coins, n):
    results = [1] + [0] * n
    for coin in coins:
        for i in range(coin, n + 1):
            results[i] += results[i - coin]
    return results[n]



# notes:

"""
0: 1 way
1: 1 way
2: 2 ways
3: 3 ways
4: 4 ways
5: 5 ways
6: 7 ways
7: 8 ways
"""


def make_change(coins, n):
	coins = list(coins)
	for c in coins:
		for i in range(n//c + 1):
			make_change(list(coins), n - i*c)

n = 7
solutions = 0
for x in range(n//1+1):
	for y in range((n-x*1)//2+1):
		for z in range((n-x*1-y*2)//3+1):
			if x*1 + y*2 + z*3 == n:
				solutions += 1
print(solutions)


def ways(coins, n):
	coin = coins.pop(0)
	if not coins:
		return int(n % coin == 0)
	num = 0
	for i in range(n//coin+1):
		num += ways(list(coins), n-i*coin)
	return num

def ways(coins, n):
	coin = coins.pop(0)
	if not coins:
		return int(n % coin == 0)
	return sum(ways(list(coins), n-i*coin) for i in range(n//coin+1))

def ways(coins, n):
	coin = coins.pop(0)
	return sum(ways(list(coins), n-i*coin) for i in range(n//coin+1)) if coins else int(n % coin == 0)

def ways(coins, n):
	return sum(ways(list(coins[1:]), n-i*coins[0]) for i in range(n//coins[0]+1)) if len(coins) > 1 else int(n % coins[0] == 0)


def ways(coins, n):
	if not coins:
		return int(n == 0)
	coin = coins.pop(0)
	num = 0
	for i in range(n//coin+1):
		num += ways(list(coins), n-i*coin)
	return num



def make_change(coins, n):
  if 'D' not in make_change.__dict__:
  	make_change.D = {}
  id = set(coins), n
  if id not in make_change.D:
			coin = coins.pop(0)
			if coins:
				make_change.D[id] = sum(make_change(list(coins), n-i*coin) for i in range(n//coin+1))
			make_change.D[id] = int(n % coin == 0)
  return make_change.d[id]



n = 7
solutions = 0
for x in range(n//1+1):
	for y in range((n-x*1)//2+1):
		if (n-x*1-y*2) % 3 == 0:
			solutions += 1
print(solutions)

solutions = set()
for x in range(n//1+1):
	for y in range(n//2+1):
		for z in range(n//3+1):
			if x*1 + y*2 + z*3 == n:
				solutions.add((x, y, z))
print(len(solutions))