All Paths From Source to Target LeetCode solution in Java

1
// Approach : Using dfs+ backtracking we can solve it
2

3
class Solution {
4
  public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
5
    List<List<Integer>> ans = new ArrayList<>();
6
    List<Integer> temp = new ArrayList<>();
7
    boolean[] visit = new boolean[graph.length];
8
    helper(graph, 0, graph.length - 1, ans, temp, visit);
9

10
    return ans;
11
  }
12

13
  public void helper(
14
      int[][] graph,
15
      int src,
16
      int dest,
17
      List<List<Integer>> ans,
18
      List<Integer> temp,
19
      boolean[] vis) {
20
    vis[src] = true;
21
    temp.add(src);
22

23
    if (src == dest) {
24
      List<Integer> b = new ArrayList<>();
25
      for (int h : temp) {
26
        b.add(h);
27
      }
28
      ans.add(b);
29
    }
30

31
    for (int i : graph[src]) {
32
      if (vis[i] != true) {
33
        helper(graph, i, dest, ans, temp, vis);
34
      }
35
    }
36

37
    vis[src] = false;
38
    temp.remove(temp.size() - 1);
39
  }
40
}