> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/06-29-2022-797.-all-paths-from-source-to-target.md).

# 06/29/2022 797. All Paths From Source to Target

Method: use dfs backtracking. First we add the node to the path. The base case is when the node == graph.size() - 1, we add current path to the result and return. Otherwise, we iterate the adjacent nodes of this current nodes and perform dfs on it. finally we need remove it from the path. 

Time O(2 ^V ⋅V)

Space O(V)

```
// Some code
class Solution {
    // DFS
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> paths = new ArrayList<>();
        if (graph == null || graph.length == 0) {
            return paths;
        }

        dfs(graph, 0, new ArrayList<>(), paths);
        return paths;
    }

    void dfs(int[][] graph, int node, List<Integer> path, List<List<Integer>> paths) {
        path.add(node);
        if (node == graph.length - 1) {
            paths.add(new ArrayList<>(path));
            return;
        }
        int[] nextNodes = graph[node];
        for (int nextNode: nextNodes) {
            dfs(graph, nextNode, path, paths);
            path.remove(path.size() - 1);
        }
    }
}
```