Problem Description
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.
Example 2:
Input: graph = [[4,3,1],[3,2,4],[3],[4],[]] Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
Example 3:
Input: graph = [[1],[]] Output: [[0,1]]
Example 4:
Input: graph = [[1,2,3],[2],[3],[]] Output: [[0,1,2,3],[0,2,3],[0,3]]
Example 5:
Input: graph = [[1,3],[2],[3],[]] Output: [[0,1,2,3],[0,3]]
Constraints:
n == graph.length2 <= n <= 150 <= graph[i][j] < ngraph[i][j] != i(i.e., there will be no self-loops).- All the elements of
graph[i]are unique. - The input graph is guaranteed to be a DAG.
The description was taken from https://leetcode.com/problems/all-paths-from-source-to-target/.
Problem Solution
#O(N*2^N) Time, O(N*2^N) Space
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
n = len(graph) - 1
adjacency, output = {}, []
for i, neighbors in enumerate(graph):
if i not in adjacency:
adjacency[i] = []
for neighbor in neighbors:
adjacency[i].append(neighbor)
def backtrack(start:int, combo:list) -> None:
if start == n:
output.append(list(combo)) return
for neighbor in adjacency[start]:
combo.append(neighbor)
backtrack(neighbor, combo)
combo.pop()
backtrack(0, [0])
return output
Problem Explanation
The problem description states that we should return all possible paths from the source to the target.
When we see a requirement like that, backtracking is typically a good approach because we would need to generate all of these possible paths.
Backtracking is a Depth-First Search algorithm where we remove a choice whenever the DFS path yoyo returns to the given function. This allows us to circulate elements into each valid position so that we can generate each valid combination.
A general template for backtracking is to set a base case that appends a valid combination for a given DFS path to the output, check if a placement is valid, then make the placement. Once that placement is made, we'd go down a new DFS path with that placement and if that path didn't lead to a solution or it didn't lead to every solution like in this problem, we'd backtrack on the choice to make that placement by removing it from the combination.
To solve this problem, we can circulate in each neighbor for each node within each DFS path.
Let's start by getting the destination node by getting the length of the input and subtracting one by it since it begins at index zero.
n = len(graph) - 1
We'll also initialize an adjacency list and an output array for valid paths.
adjacency, output = {}, []
For each node index and the list of their neighbors within the graph matrix, we will map the neighbor node numbers to the node number within our adjacency list.
for i, neighbors in enumerate(graph):
if i not in adjacency:
adjacency[i] = []
for neighbor in neighbors:
adjacency[i].append(neighbor)
Next, we will make our backtrack function.
The function will take a starting node to continue the DFS path from and a combo for the path traversed.
def backtrack(start:int, combo:list) -> None:
If the starting node is the destination node, we have a valid path so we will append the combo to the output and return from this path since we are already at the destination.
if start == n:
output.append(list(combo)) return
Otherwise, we will continue the path down each neighbor node for the given starting node.
for neighbor in adjacency[start]:
We will append a neighbor to the output, backtrack with that neighbor and path combo, then once we reach the destination or exhaust the paths that this neighbor leads to, we will pop the neighbor off the combo.
This will allow us to try each neighbor for each DFS path.
combo.append(neighbor)
backtrack(neighbor, combo)
combo.pop()
Now that we have our backtrack function built, we just need to make the initial call from the source node and return the output of valid paths from the source to the target.
backtrack(0, [0])
return output