All Paths From Source to Target (LeetCode 797) – Problem Description, Analysis, and Multi‑Language Solutions

LeetCode 797 – "All Paths From Source to Target" – asks you to find every possible path from node 0 to node n‑1 in a directed acyclic graph (DAG). The input is an adjacency list graph[i] where each entry lists the nodes reachable directly from node i.

Problem description : Given a DAG with n nodes, output all paths from the source (node 0) to the target (node n‑1). The order of the paths does not matter.

Examples :

Input: graph = [[1,2],[3],[3],[]] → Output: [[0,1,3],[0,2,3]] Input: graph = [[4,3,1],[3,2,4],[3],[4],[]] → Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]] Constraints :

n == graph.length

2 ≤ n ≤ 15

0 ≤ graph[i][j] < n

No self‑loops ( graph[i][j] != i)

All entries in graph[i] are distinct

The input is guaranteed to be a DAG

Problem analysis : Because the graph is acyclic, a depth‑first search (DFS) from node 0 can explore every possible route without risking infinite loops. When the DFS reaches node n‑1, the current traversal path is stored as a valid result. Backtracking (removing the last node from the path) is required after exploring each branch.

Java solution :

public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    path.add(0); // start node
    dfs(graph, 0, ans, path);
    return ans;
}

private void dfs(int[][] graph, int index, List<List<Integer>> ans, List<Integer> path) {
    if (index == graph.length - 1) {
        ans.add(new ArrayList<>(path));
        return;
    }
    int[] directs = graph[index];
    for (int i = 0; i < directs.length; i++) {
        path.add(directs[i]); // choose next node
        dfs(graph, directs[i], ans, path);
        path.remove(path.size() - 1); // backtrack
    }
}

C++ solution :

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
    vector<vector<int>> ans;
    vector<int> path;
    path.push_back(0);
    dfs(graph, 0, ans, path);
    return ans;
}

void dfs(vector<vector<int>>& graph, int index, vector<vector<int>>& ans, vector<int>& path) {
    if (index == graph.size() - 1) {
        ans.emplace_back(path);
        return;
    }
    for (int g : graph[index]) {
        path.emplace_back(g);
        dfs(graph, g, ans, path);
        path.pop_back(); // backtrack
    }
}

C solution (LeetCode style) :

void dfs(int** graph, int graphSize, int* graphColSize, int* returnSize, int** returnColumnSizes, int** ans, int* path, int v, int count) {
    if (v == graphSize - 1) {
        ans[*returnSize] = malloc(count * sizeof(int));
        memcpy(ans[*returnSize], path, count * sizeof(int));
        (*returnColumnSizes)[(*returnSize)++] = count;
        return;
    }
    for (int i = 0; i < graphColSize[v]; ++i) {
        path[count++] = graph[v][i];
        dfs(graph, graphSize, graphColSize, returnSize, returnColumnSizes, ans, path, graph[v][i], count);
        count--;
    }
}

int** allPathsSourceTarget(int** graph, int graphSize, int* graphColSize, int* returnSize, int** returnColumnSizes) {
    int** ans = malloc(20000 * sizeof(int*));
    int* path = malloc(15 * sizeof(int));
    int v = 0, count = 0;
    *returnSize = 0;
    *returnColumnSizes = malloc(20000 * sizeof(int));
    path[count++] = v; // start node
    dfs(graph, graphSize, graphColSize, returnSize, returnColumnSizes, ans, path, v, count);
    return ans;
}

Python solution :

def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
    def dfs(index):
        if index == len(graph) - 1:
            ans.append(path[:])
            return
        for direct in graph[index]:
            path.append(direct)  # choose
            dfs(direct)
            path.pop()          # backtrack
    ans = []
    path = [0]
    dfs(0)
    return ans

All four implementations follow the same DFS‑backtracking strategy, guaranteeing that every source‑to‑target path in the DAG is enumerated.