Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/797.html

797. All Paths From Source to Target

Level

Medium

Description

Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows: the nodes are 0, 1, …, graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:

Input: [[1,2], [3], [3], []] 
Output: [[0,1,3],[0,2,3]] 
Explanation: The graph looks like this:
0--->1
|    |
v    v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Note:

  • The number of nodes in the graph will be in the range [2, 15].
  • You can print different paths in any order, but you should keep the order of nodes inside one path.

Solution

Use breadth first search. Starting from node 0, each time obtain the next nodes from graph, and move to the next nodes. For each node visited, maintain the current path as well. If the target node N-1 is met, add the path to the result list. Finally, return the result list.

  • class Solution {
        public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
            List<List<Integer>> allPathsList = new ArrayList<List<Integer>>();
            int nodes = graph.length;
            int target = nodes - 1;
            Queue<Integer> nodesQueue = new LinkedList<Integer>();
            Queue<List<Integer>> pathsQueue = new LinkedList<List<Integer>>();
            nodesQueue.offer(0);
            List<Integer> initialList = new ArrayList<Integer>();
            initialList.add(0);
            pathsQueue.offer(initialList);
            while (!nodesQueue.isEmpty()) {
                int node = nodesQueue.poll();
                List<Integer> prevPath = pathsQueue.poll();
                int[] nextNodes = graph[node];
                for (int nextNode : nextNodes) {
                    List<Integer> curPath = new ArrayList<Integer>(prevPath);
                    curPath.add(nextNode);
                    if (nextNode == target)
                        allPathsList.add(curPath);
                    else {
                        nodesQueue.offer(nextNode);
                        pathsQueue.offer(curPath);
                    }
                }
            }
            return allPathsList;
        }
    }
    
    ############
    
    class Solution {
        public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
            int n = graph.length;
            Queue<List<Integer>> queue = new ArrayDeque<>();
            queue.offer(Arrays.asList(0));
            List<List<Integer>> ans = new ArrayList<>();
            while (!queue.isEmpty()) {
                List<Integer> path = queue.poll();
                int u = path.get(path.size() - 1);
                if (u == n - 1) {
                    ans.add(path);
                    continue;
                }
                for (int v : graph[u]) {
                    List<Integer> next = new ArrayList<>(path);
                    next.add(v);
                    queue.offer(next);
                }
            }
            return ans;
        }
    }
    
    
  • // OJ: https://leetcode.com/problems/all-paths-from-source-to-target/
    // Time: O(N * 2^N)
    // Space: O(N) extra space
    class Solution {
    public:
        vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& G) {
            vector<int> path;
            vector<vector<int>> ans;
            int N = G.size();
            function<void(int)> dfs = [&](int u) {
                path.push_back(u);
                if (u == N - 1) ans.push_back(path);
                else {
                    for (int v : G[u]) dfs(v);
                }
                path.pop_back();
            };
            dfs(0);
            return ans;
        }
    };
    
  • class Solution:
        def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
            n = len(graph)
            q = deque([[0]])
            ans = []
            while q:
                path = q.popleft()
                u = path[-1]
                if u == n - 1:
                    ans.append(path)
                    continue
                for v in graph[u]:
                    q.append(path + [v])
            return ans
    
    ############
    
    class Solution(object):
        def allPathsSourceTarget(self, graph):
            """
            :type graph: List[List[int]]
            :rtype: List[List[int]]
            """
            res = []
            self.dfs(graph, res, 0, [0])
            return res
            
        
        def dfs(self, graph, res, pos, path):
            if pos == len(graph) - 1:
                res.append(path)
                return
            else:
                for n in graph[pos]:
                    self.dfs(graph, res, n, path + [n])
    
  • func allPathsSourceTarget(graph [][]int) [][]int {
    	var path []int
    	path = append(path, 0)
    	var ans [][]int
    
    	var dfs func(i int)
    	dfs = func(i int) {
    		if i == len(graph)-1 {
    			ans = append(ans, append([]int(nil), path...))
    			return
    		}
    		for _, j := range graph[i] {
    			path = append(path, j)
    			dfs(j)
    			path = path[:len(path)-1]
    		}
    	}
    
    	dfs(0)
    	return ans
    }
    
  • /**
     * @param {number[][]} graph
     * @return {number[][]}
     */
    var allPathsSourceTarget = function (graph) {
        const ans = [];
        const t = [0];
    
        const dfs = t => {
            const cur = t[t.length - 1];
            if (cur == graph.length - 1) {
                ans.push([...t]);
                return;
            }
            for (const v of graph[cur]) {
                t.push(v);
                dfs(t);
                t.pop();
            }
        };
    
        dfs(t);
        return ans;
    };
    
    
  • impl Solution {
        fn dfs(i: usize, path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, graph: &Vec<Vec<i32>>) {
            path.push(i as i32);
            if i == graph.len() - 1 {
                res.push(path.clone());
            }
            for j in graph[i].iter() {
                Self::dfs(*j as usize, path, res, graph)
            }
            path.pop();
        }
    
        pub fn all_paths_source_target(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
            let mut res = Vec::new();
            Self::dfs(0, &mut vec![], &mut res, &graph);
            res
        }
    }
    
    

All Problems

All Solutions