|
| 1 | +# 797. All Paths From Source to Target |
| 2 | +LeetCode problem: [797. All Paths From Source to Target](https://leetcode.com/problems/all-paths-from-source-to-target/) |
| 3 | + |
| 4 | +## LeetCode problem description |
| 5 | +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**. |
| 6 | + |
| 7 | +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]`). |
| 8 | + |
| 9 | +### Example 1 |
| 10 | + |
| 11 | +``` |
| 12 | +Input: graph = [[1,2],[3],[3],[]] |
| 13 | +Output: [[0,1,3],[0,2,3]] |
| 14 | +Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3. |
| 15 | +``` |
| 16 | + |
| 17 | +### Example 2 |
| 18 | + |
| 19 | +``` |
| 20 | +Input: graph = [[4,3,1],[3,2,4],[3],[4],[]] |
| 21 | +Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]] |
| 22 | +``` |
| 23 | + |
| 24 | +### Constraints |
| 25 | +- `n == graph.length` |
| 26 | +- `2 <= n <= 15` |
| 27 | +- `0 <= graph[i][j] < n` |
| 28 | +- `graph[i][j] != i` (i.e., there will be no self-loops). |
| 29 | +- All the elements of `graph[i]` are **unique**. |
| 30 | +- The input graph is **guaranteed** to be a **DAG**. |
| 31 | + |
| 32 | +## Thoughts |
| 33 | +This problem can be solved using **Depth-First Search of a Graph**. |
| 34 | + |
| 35 | +Detailed solutions will be given later, and now only the best practices in 7 languages are given. |
| 36 | + |
| 37 | +### Complexity |
| 38 | +* Time: `O(2**n)`. |
| 39 | +* Space: `O(n)`. |
| 40 | + |
| 41 | +## Python |
| 42 | +### Solution 1: New array as parameter |
| 43 | +```python |
| 44 | +class Solution: |
| 45 | + def __init__(self): |
| 46 | + self.paths = [] |
| 47 | + self.graph = None |
| 48 | + |
| 49 | + def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]: |
| 50 | + self.graph = graph |
| 51 | + |
| 52 | + self.dfs(0, [0]) |
| 53 | + |
| 54 | + return self.paths |
| 55 | + |
| 56 | + def dfs(self, node, path): |
| 57 | + if node == len(self.graph) - 1: |
| 58 | + self.paths.append(path.copy()) |
| 59 | + return |
| 60 | + |
| 61 | + target_nodes = self.graph[node] |
| 62 | + |
| 63 | + for target_node in target_nodes: |
| 64 | + self.dfs(target_node, path + [target_node]) |
| 65 | +``` |
| 66 | + |
| 67 | +### Solution 2: More efficient by reusing one array (recommended) |
| 68 | +```python |
| 69 | +class Solution: |
| 70 | + def __init__(self): |
| 71 | + self.paths = [] |
| 72 | + self.path = [0] |
| 73 | + self.graph = None |
| 74 | + |
| 75 | + def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]: |
| 76 | + self.graph = graph |
| 77 | + |
| 78 | + self.dfs(0) |
| 79 | + |
| 80 | + return self.paths |
| 81 | + |
| 82 | + def dfs(self, node): |
| 83 | + if node == len(self.graph) - 1: |
| 84 | + self.paths.append(self.path.copy()) |
| 85 | + return |
| 86 | + |
| 87 | + target_nodes = self.graph[node] |
| 88 | + |
| 89 | + for target_node in target_nodes: |
| 90 | + self.path.append(target_node) |
| 91 | + self.dfs(target_node) |
| 92 | + self.path.pop() |
| 93 | +``` |
| 94 | + |
| 95 | +## Java |
| 96 | +```java |
| 97 | + |
| 98 | +``` |
| 99 | + |
| 100 | +## C++ |
| 101 | +```cpp |
| 102 | +// Welcome to create a PR to complete the code of this language, thanks! |
| 103 | +``` |
| 104 | + |
| 105 | +## JavaScript |
| 106 | +```javascript |
| 107 | + |
| 108 | +``` |
| 109 | + |
| 110 | +## C# |
| 111 | +```c# |
| 112 | +``` |
| 113 | + |
| 114 | +## Go |
| 115 | +```go |
| 116 | +// Original article is at https://github.com/gazeldx/leetcode-best-practice |
| 117 | +// Welcome to create a PR to complete the code of this language, thanks! |
| 118 | +``` |
| 119 | + |
| 120 | +## Ruby |
| 121 | +```ruby |
| 122 | +# Original article is at https://github.com/gazeldx/leetcode-best-practice |
| 123 | +# Welcome to create a PR to complete the code of this language, thanks! |
| 124 | +``` |
| 125 | + |
| 126 | +## C |
| 127 | +```c |
| 128 | +// Welcome to create a PR to complete the code of this language, thanks! |
| 129 | +``` |
| 130 | + |
| 131 | +## Kotlin |
| 132 | +```kotlin |
| 133 | +// Welcome to create a PR to complete the code of this language, thanks! |
| 134 | +``` |
| 135 | + |
| 136 | +## Swift |
| 137 | +```swift |
| 138 | +// Welcome to create a PR to complete the code of this language, thanks! |
| 139 | +``` |
| 140 | + |
| 141 | +## Rust |
| 142 | +```rust |
| 143 | +// Welcome to create a PR to complete the code of this language, thanks! |
| 144 | +``` |
| 145 | + |
| 146 | +## Other languages |
| 147 | +``` |
| 148 | +// Welcome to create a PR to complete the code of this language, thanks! |
| 149 | +``` |
0 commit comments