URL

https://leetcode.com/problems/combination-sum-iv/description/?envType=daily-question&envId=2023-09-09

Code

https://github.com/syohex/dotnet-study/blob/master/fsharp/leetcode/challenge/202309/combination_sum4/main.fsx

let combinationSum4 (nums: int list) (target: int) : int =
    let rec combinationSum4' target nums cache =
        if target = 0 then
            1, cache
        else
            match Map.tryFind target cache with
            | Some(v) -> v, cache
            | None ->
                let ret, cache' =
                    nums
                    |> List.filter (fun num -> target - num >= 0)
                    |> List.fold
                        (fun (acc, cache) num ->
                            let ret, cache' = combinationSum4' (target - num) nums cache
                            acc + ret, cache')
                        (0, cache)

                ret, Map.add target ret cache'

    combinationSum4' target nums Map.empty |> fst