I had this one all wrong, and made it way more complex than it really was. I’m embarassed to post the final code … but it is what it is.

**Statutory Warning**: *Spoilers ahead*

```
import Data.Maybe
-- Basic idea is something like this:
-- [*] given amount and some coins, pick the largest coin
-- [*] there are (floor (total/coin)) ways of using this coin value
-- [*] but ... NOT ALL of these count! Only the ones that leave a total that can be used with the remaining coins!
coins = [1, 2, 5, 10, 20, 50, 100, 200]
sortedCoins :: [Int]
sortedCoins = L.reverse $ L.sort $ coins
combinations :: Int -> [Int] -> Maybe Int
combinations total coins =
-- T.trace ("total = " ++ show total ++ ", coins = " ++ show coins) $
if total == 0
then Just 1
else case coins of
[] -> Nothing
[c] -> if mod total c == 0 then Just 1 else Nothing
c:cs -> if total == 0
then Just 1
else let newTotal total coin num = total - (coin * num)
combs = [combinations (newTotal total c num) cs | num <- [0 .. div total c]]
counts = sum $ catMaybes combs
in
if counts == 0 then Nothing else Just counts
euler31 :: Int
euler31 = fromJust $ combinations 200 sortedCoins
```

It turns out, I was being overly cautious and could have just used lists in a different way (left in a commented out debug line to show that I needed it).