Algorithm
Problem Name: 797. All Paths From Source to Target
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]]
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.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<vector<int>> allPathsSourceTarget(vector < vector<int>>& graph) {
vector < vector<int>>res;
dfs(graph, res, {}, 0);
return res;
}
void dfs(vector < vector<int>>& graph, vector < vector<int>>& res, vector<int> path, int node){
path.push_back(node);
if(graph[node].size() == 0) res.push_back(path);
for(int neigh: graph[node]) dfs(graph, res, path, neigh);
}
};
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List();
int target = graph.length - 1;
List < Integer> temp = new ArrayList<>();
temp.add(0);
helper(list, temp, 0, graph, target);
return list;
}
private void helper(List < List temp, int curr, int[][] graph, int target) {
if (curr == target) {
list.add(new ArrayList<>(temp));
}
else {
int[] connections = graph[curr];
for (int connection : connections) {
temp.add(connection);
helper(list, temp, connection, graph, target);
temp.remove(temp.size() - 1);
}
}
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const allPathsSourceTarget = function(graph) {
const res = []
const path = []
bt(graph, res, path, 0)
return res
};
function bt(g, res, path, cur) {
path.push(cur)
if(cur === g.length - 1) res.push(path.slice())
else {
for(let i of g[cur]) bt(g, res, path, i)
}
path.pop()
}
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def allPathsSourceTarget(self, graph, i = 0, q = [0]):
if i == 0:
global res
res = []
if i == len(graph) - 1:
res.append(q)
for index in graph[i]:
self.allPathsSourceTarget(graph, index, q + [index])
return res
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0797_AllPathsFromSourceToTarget
{
public IList < IList<int>> AllPathsSourceTarget(int[][] graph)
{
var cache = new Dictionary < int, IList();
return AllPathsSourceTarget(graph, 0, cache);
}
private IList < IList<int>> AllPathsSourceTarget(int[][] graph, int node, Dictionary < int, IList cache)
{
if (cache.ContainsKey(node))
return cache[node];
var results = new List < IList<int>>();
foreach (var next in graph[node])
{
if (next == graph.Length - 1)
results.Add(new List < int>() { node, next });
var pathes = AllPathsSourceTarget(graph, next, cache);
if (pathes.Count > 0)
{
foreach (var path in pathes)
{
var newPath = new List < int>();
newPath.Add(node);
newPath.AddRange(path);
results.Add(newPath);
}
}
}
cache[node] = results;
return results;
}
}
}
Input
Output