All Paths From Source to Target - LeetCode
Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order. The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).
Example 1:
Input: graph = [[1,2],[3],[3],[]] Output: [[0,1,3],[0,2,3]] Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
- code
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
target = len(graph) - 1
results = []
def backtrack(currNode, path):
# if we reach the target, no need to explore further.
if currNode == target:
results.append(list(path))
return
# explore the neighbor nodes one after another.
for nextNode in graph[currNode]:
path.append(nextNode)
backtrack(nextNode, path)
path.pop()
# kick of the backtracking, starting from the source node (0).
path = deque([0])
backtrack(0, path)
return results
- code
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
res = []
def dfs(cur, path):
if cur == len(graph) - 1:
res.append(path + [cur])
return
for next_node in graph[cur]:
dfs(next_node, path + [cur])
dfs(0, [])
return res