All Paths From Source to Target

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> out;
        vector<int> path = {0};
        const int target = graph.size() - 1;
        function<void(int)> dfs = [&](int u) {
            if (u == target) { out.push_back(path); return; }
            for (int v : graph[u]) {
                path.push_back(v);
                dfs(v);
                path.pop_back();
            }
        };
        dfs(0);
        return out;
    }
};

func allPathsSourceTarget(graph [][]int) [][]int {
    out := [][]int{}
    path := []int{0}
    target := len(graph) - 1
    var dfs func(int)
    dfs = func(u int) {
        if u == target {
            cp := make([]int, len(path))
            copy(cp, path)
            out = append(out, cp)
            return
        }
        for _, v := range graph[u] {
            path = append(path, v)
            dfs(v)
            path = path[:len(path)-1]
        }
    }
    dfs(0)
    return out
}

from typing import List

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        out: List[List[int]] = []
        target = len(graph) - 1
        path: List[int] = [0]

        def dfs(u: int) -> None:
            if u == target:
                out.append(path.copy())
                return
            for v in graph[u]:
                path.append(v)
                dfs(v)
                path.pop()

        dfs(0)
        return out

var allPathsSourceTarget = function(graph) {
    const out = [];
    const path = [0];
    const target = graph.length - 1;
    const dfs = (u) => {
        if (u === target) { out.push([...path]); return; }
        for (const v of graph[u]) {
            path.push(v);
            dfs(v);
            path.pop();
        }
    };
    dfs(0);
    return out;
};

class Solution {
    private int[][] graph;
    private int target;
    private List<List<Integer>> out;
    private Deque<Integer> path;

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        this.graph = graph;
        this.target = graph.length - 1;
        this.out = new ArrayList<>();
        this.path = new ArrayDeque<>();
        path.offer(0);
        dfs(0);
        return out;
    }

    private void dfs(int u) {
        if (u == target) {
            out.add(new ArrayList<>(path));
            return;
        }
        for (int v : graph[u]) {
            path.offer(v);
            dfs(v);
            path.pollLast();
        }
    }
}

function allPathsSourceTarget(graph: number[][]): number[][] {
    const out: number[][] = [];
    const path: number[] = [0];
    const target = graph.length - 1;
    const dfs = (u: number): void => {
        if (u === target) { out.push([...path]); return; }
        for (const v of graph[u]) {
            path.push(v);
            dfs(v);
            path.pop();
        }
    };
    dfs(0);
    return out;
}