All Paths From Source to Target(2 Methods) | LeetCode | Java

Method 1 : Using Visited Array - DFS

class Solution {
    List<List<Integer>> resList;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int len = graph.length;
        List<Integer> path = new ArrayList<>();
        resList = new ArrayList<>();
        boolean visited[] = new boolean[len];
        dfs(graph, 0, len-1, visited, path);
        return resList;
    }
      void dfs(int graph[][], int src, int dest, boolean visited[], List<Integer> path) {
        visited[src] = true;
        path.add(src);

        if (src == dest) {
            resList.add(new ArrayList<>(path));
        }

        for (int ele : graph[src]) {
            if (!visited[ele]) 
                dfs(graph, ele, dest, visited, path);
        }

        path.remove(path.size() - 1);
        visited[src] = false;
    }
}

Method 2 : Using Backtracking

class Solution {
    List<List<Integer>> resList;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {

        resList = new ArrayList<>();
        int n = graph.length;
        int src = 0;
        int dest = n-1;
        List<Integer> path = new ArrayList<>();
        path.add(0);

        getPaths(graph, src, dest, path);
        return resList;
    }

    void getPaths(int graph[][], int src, int dest, List<Integer> path){

        if(src==dest){
            resList.add(new ArrayList<>(path));
            return;
        }

        else{
              for(int ele : graph[src]){
                  path.add(ele);
                  getPaths(graph, ele, dest, path);
                  path.remove(path.size()-1);
              }
        }

    }
}

Thanks for reading :)
Feel free to comment and like the post if you found it helpful
Follow for more 🤝 && Happy Coding 🚀

If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7