797. All Paths From Source to Target

 一刷 06/2022

Version #1 DFS

Time - given that there are N nodes, there could be at most have 2^N - 1 paths from start to end, and for the path there could be N - 2 nodes

O(2N⋅N)

Space 

O(2N⋅N)

Runtime: 1 ms, faster than 99.86% of Java online submissions for All Paths From Source to Target.

Memory Usage: 44.1 MB, less than 90.00% of Java online submissions for All Paths From Source to Target.

class Solution {

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {

        if (graph == null || graph.length == 0) {

            return new ArrayList<>();

        }

        boolean[] visited = new boolean[graph.length];

        visited[0] = true;

        List<List<Integer>> result = new ArrayList<>();

        dfs(graph, visited, 0, new ArrayList<>(), result);

        return result;

    }

    

    private void dfs(int[][] graph, boolean[] visited, int node, List<Integer> path, List<List<Integer>> result) {

        path.add(node);

        if (node == graph.length - 1) {

            result.add(new ArrayList<>(path));

            path.remove(path.size() - 1);

            return;

        }

        for (int next : graph[node]) {

            if (visited[next]) {

                continue;

            }

            visited[next] = true;

            dfs(graph, visited, next, path, result);

            visited[next] = false;

        }

        path.remove(path.size() - 1);

    }

}