URL

https://leetcode.com/problems/all-paths-from-source-to-target/description/

Code

https://github.com/syohex/dotnet-study/blob/master/fsharp/leetcode/problems/0797/main.fsx

let allPathsSourceTarget (graph: int list []) : int list list =
    let target = graph.Length - 1

    let rec allPathsSourceTarget' q target (graph: int list []) acc =
        match q with
        | [] -> acc
        | (node, path, visited) :: t ->
            if node = target then
                allPathsSourceTarget' t target graph ((path |> List.rev) :: acc)
            else
                let visited' = Set.add node visited

                let q' =
                    graph.[node]
                    |> List.fold
                        (fun acc n ->
                            if Seq.contains n visited' then
                                acc
                            else
                                (n, (n :: path), visited') :: acc)
                        t

                allPathsSourceTarget' q' target graph acc

    let q = [ (0, [ 0 ], Set.empty) ]
    allPathsSourceTarget' q target graph []