LeetCode Entry

797. All Paths From Source to Target

30.12.2022 medium 2022 kotlin

fun allPathsSourceTarget(graph: Array): List> {

797. All Paths From Source to Target medium

https://t.me/leetcode_daily_unstoppable/68

blog post

    fun allPathsSourceTarget(graph: Array<IntArray>): List<List<Int>> {
        val res = mutableListOf<List<Int>>()
        val currPath = mutableListOf<Int>()
        fun dfs(curr: Int) {
            currPath += curr
            if (curr == graph.lastIndex) res += currPath.toList()
            graph[curr].forEach { dfs(it) }
            currPath.removeAt(currPath.lastIndex)
        }
        dfs(0)
        return res
    }

We must find all the paths, so there is no shortcuts to the visiting all of them. One technique is backtracking - reuse existing visited list of nodes.

Space: O(VE), Time: O(VE)