Project Euler — Problem 76 Solution

Problem

It is pos­si­ble to write five as a sum in exact­ly six dif­fer­ent ways:

4 + 1

3 + 2

3 + 1 + 1

2 + 2 + 1

2 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1

How many dif­fer­ent ways can one hun­dred be writ­ten as a sum of at least two pos­i­tive inte­gers?

Solution

// implement the coin change algorithm
let rec count n m (coins:int list) =
    if n = 0 then 1
    else if n < 0 then 0
    else if (m <= 0 && n >= 1) then 0
    else (count n (m-1) coins) + (count (n-coins.[m-1]) m coins)

let answer = count 100 99 [1..99]

This is basi­cal­ly prob­lem 31 with a twist, using the same coin change algo­rithm but sub­sti­tute the set coins with the num­bers less than 100 and you’ll have your solu­tion!