All Paths From Source to Target - Practice Coding Problems

All Paths From Source to Target - Problem

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

Input & Output

Example 1 — Basic DAG

$ Input: graph = [[1,2],[3],[3],[]]

› Output: [[0,1,3],[0,2,3]]

💡 Note: There are two paths from node 0 to node 3: Path 1 goes 0→1→3, and Path 2 goes 0→2→3. Both paths reach the target node 3.

Example 2 — Single Path

$ 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]]

💡 Note: There are 5 different paths from node 0 to node 4. Each path represents a different route through the DAG to reach the target.

Example 3 — Linear Path

$ Input: graph = [[1],[2],[]]

› Output: [[0,1,2]]

💡 Note: Only one path exists: 0→1→2. This is a simple linear path from source to target.

Constraints

n == graph.length
2 ≤ n ≤ 15
0 ≤ graph[i][j] < n
graph[i][j] != i (i.e., there will be no self-loops)
All the elements of graph[i] are unique
The input graph is guaranteed to be a DAG

Visualization

Tap to expand

Understanding the Visualization

Input Graph

DAG with nodes 0 to n-1, adjacency list representation

Explore Paths

Use DFS to find all paths from node 0 to node n-1

Collect Results

Return all complete paths as list of lists

Key Takeaway

🎯 Key Insight: Use DFS with backtracking to systematically explore all paths while maintaining the current path state

Asked in

f Facebook 12 a Amazon 8 G Google 6

The key insight is to use DFS with backtracking to systematically explore all possible paths from source to target in the DAG. Best approach is DFS with backtracking which naturally handles path construction and restoration. Time: O(2^N × N), Space: O(N)

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking Approach	O(2^N × N)	O(N)	Classic backtracking with explicit path construction and restoration
Optimized DFS	O(2^N × N)	O(N)	Depth-first search with path tracking and early termination
Brute Force DFS	O(2^N × N)	O(2^N × N)	Simple recursive DFS to explore all paths without optimization

Backtracking Approach — Algorithm Steps

Start with empty result and path containing source node
For current node, try each neighbor
Add neighbor to path and recurse
After exploring, remove neighbor from path (backtrack)
Collect complete paths when target is reached

Visualization

Tap to expand

Step-by-Step Walkthrough

Choose

Make a choice by adding neighbor to path

Recurse

Explore that choice recursively

Undo

Remove choice from path and try next option

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int** result;
int* resultSizes;
int resultCount;
int resultCapacity;

void backtrack(int** graph, int* graphColSize, int node, int target, int* path, int pathSize) {
    // Base case: reached target
    if (node == target) {
        if (resultCount >= resultCapacity) {
            resultCapacity *= 2;
            result = realloc(result, resultCapacity * sizeof(int*));
            resultSizes = realloc(resultSizes, resultCapacity * sizeof(int));
        }
        
        result[resultCount] = malloc(pathSize * sizeof(int));
        for (int i = 0; i < pathSize; i++) {
            result[resultCount][i] = path[i];
        }
        resultSizes[resultCount] = pathSize;
        resultCount++;
        return;
    }
    
    // Try each neighbor
    for (int i = 0; i < graphColSize[node]; i++) {
        // Make choice
        path[pathSize] = graph[node][i];
        // Recurse
        backtrack(graph, graphColSize, graph[node][i], target, path, pathSize + 1);
        // Backtrack (automatic with function return)
    }
}

int main() {
    int graph0[] = {1, 2};
    int graph1[] = {3};
    int graph2[] = {3};
    int* graph[] = {graph0, graph1, graph2, NULL};
    int graphColSize[] = {2, 1, 1, 0};
    
    resultCapacity = 10;
    result = malloc(resultCapacity * sizeof(int*));
    resultSizes = malloc(resultCapacity * sizeof(int));
    resultCount = 0;
    
    int path[100];
    path[0] = 0;
    backtrack(graph, graphColSize, 0, 3, path, 1);
    
    printf("[");
    for (int i = 0; i < resultCount; i++) {
        printf("[");
        for (int j = 0; j < resultSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < resultSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < resultCount - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^N × N)

Explores all possible paths in DAG, copying each complete path takes O(N) time

✓ Linear Growth

Space Complexity

O(N)

Recursion stack depth at most N, plus temporary path storage

✓ Linear Space

125.0K Views

Medium Frequency

~15 min Avg. Time

4.3K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Backtracking Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler