797. All Paths From Source to Target.md

797. All Paths From Source to Target

---

Difficulty : Medium

Related Topics : DFS

---

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

• mine
  • Java
    • DFS Runtime: 2 ms, faster than 98.93%, Memory Usage: 41.2 MB, less than 49.80% of Java online submissions

      public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
          int n = graph.length;
          boolean[] used = new boolean[n];
          List<List<Integer>> res = new ArrayList<>();
          dfs(res, new ArrayList<>(), graph, used, 0);
          return res;
      }
      
      void dfs(List<List<Integer>> res, List<Integer> list, int[][] graph, boolean[] used, int s) {
          used[s] = true;
          list.add(s);
          for (int i : graph[s]) {
              if (used[i]) {
                  continue;
              }
              if (i + 1 == used.length) {
                  List<Integer> t = new ArrayList<>();
                  t.addAll(list);
                  t.add(i);
                  res.add(t);
              } else {
                  dfs(res, list, graph, used, i);
                  used[i] = false;
                  list.remove(list.size() - 1);
              }
          }
      }
      

---

• the most votes

• Runtime: 2 ms, faster than 99.87%,Memory Usage: 40.9 MB, less than 100.00% of Java online submissions

  public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
      List<List<Integer>> res = new ArrayList<>();
      List<Integer> path = new ArrayList<>();
  
      path.add(0);
      deepSearch(graph, 0, path, res);
  
      return res;
  }
  
  public void deepSearch(int[][] graph, int index, List<Integer> path, List<List<Integer>> res) {
      if (index + 1 == graph.length) {
          res.add(new ArrayList<>(path));
          return;
      }
      for (int node : graph[index]) {
          path.add(node);
          deepSearch(graph, node, path, res);
          path.remove(path.size() - 1);
      }
  }
  

---