#### Problem

It is possible to write five as a sum in exactly six different ways:

4 + 1

3 + 2

3 + 1 + 1

2 + 2 + 1

2 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

#### 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 basically problem 31 with a twist, using the same coin change algorithm but substitute the set coins with the numbers less than 100 and you’ll have your solution!

Pingback: Project Euler - Problem 77 Solution | theburningmonk.com()