ways, coins used for n cents

Count number of ways and coins used for n cents given set of coins.

coins = { 5, 10, 25 }

// without caching
count-ways(n, coins = [5, 10, 25]):
    if n <= 0:
        return 0
    return (n, coins)
count-ways(n, coins):
    if n == 0:
        return 1
    if n < 0:
        return 0
    ncount = 0
    for coin in coins:
        ncount += (n -coin, coins)
    return ncount

count-ways(10) =2
    (5)
        (0) =1
    (0) =1

count-ways(7) =0
    (2) =0
        (-3) =0

Tweak: Count only unique combinations.

// assume coins are sorted asc
// without caching
(n, coins = [5, 10, 25], starti = 0):
    if n == 0:
        return 1
    if n < 0:
        return 0
    ncount = 0
    for i = starti, i < coins.length(), i++:
        coin = coins[i]
        ncount += (n -coin, coins, i)
    return ncount

(15)
    5,5,5
    5,10
    10,5 // do not return this

For coin count, the base case (n < 0) cannot return 0, but null. The base case but one (example n = 2) also cannot return 0 as n = 7 will return 1 instead of null. A nullable return type works but with caching a tuple (isvalid, count) gives clarity.

int count-coins(n, coins = [ ... ]):
    return (n, coins).value
    
(bool, int) count-coins-inner(n, coins = [ ... ], cache):
    if n < 0:
        return (false, 0)
    if n == 0:
        return (true, 0)
    if cache[n-1] != null:
        return cache[n-1]
    ncount = 0
    nisvalid = false
    for coin in coins:
        isvalid, count = (n -coin, coins)
        nisvalid |= isvalid
        if isvalid:
            ncount += 1 +count
    cache[n-1] = (nisvalid, ncount)
    return (nisvalid, ncount)

count-coins-inner(10) =(true,3)
    (5) =(true,1)
        (0) =(true,0)
    (0) =(true,0)

count-coins-inner(7) =(false, 0)
    (2) =(false, 0)
        (-3)=(false, 0)

[Hat tip to ctci]