Coins.fs

let coins = [50;22;19;17;10;7;5;3;2;1;1;1;1;1] |> List.sortBy (fun x -> -x)

let rec take coins coin = 
    match coins with
    | x::xs when x > coin -> take xs coin
    | x::xs when x < coin -> []
    | x::xs when x = coin -> xs
    | [] -> []

let rec change (coins:list<int>) (amt:int) = 
    let less = List.filter (fun x -> x <= amt) coins
    match less with
    | [] -> [[]]
    | _ -> 
        let unique = less |> Seq.distinct |> Seq.sortDescending |> Seq.toList
        let variants = unique |> List.map (fun first -> 
            let remaining = amt - first
            if remaining = 0 then
                [[first]]
            else
                let rest = take coins first
                let tails = change rest remaining
                tails |> List.filter (fun l -> List.length l > 0) |> List.map (fun t -> first :: t)) |> List.concat
        variants
        
let dumpToString ways =
    let strs = ways |> List.map (fun x1 -> String.Join ("; ", (x1 |> List.map (fun xx -> xx.ToString()) |> List.toArray)))
    strs.Dump()

change coins 54 |> dumpToString
change coins 55 |> dumpToString
change coins 56 |> dumpToString