797. All Paths From Source to Target

Q: Why doesn't this need visited tracking?

Because the graph is a DAG — no cycles. Without cycles, you can't loop back, so visited is implicit. If cycles were possible, you'd need a visited set per path (or accept potential infinite loops).

Q: Could you use memoization for speedup?

Not for path enumeration — the number of paths can be exponential, so any caching of 'paths from node X' uses exponential memory. For PATH COUNT (not enumeration), memo on count(node) is O(n + edges).

mediumAsked at LinkedIn

Given a DAG with n nodes labeled 0 to n-1, find all possible paths from node 0 to node n-1. LinkedIn asks this on the graph traversal round — they want clean DFS with path tracking, no DP needed (because it's a DAG and paths could be exponential).

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in LinkedIn loops.

Glassdoor (2026-Q1)— LinkedIn SWE onsite reports cite this as the graph DFS warmup before a harder follow-up.
Blind (2025-12)— LinkedIn writeups specifically describe this as their go-to graph-DFS question.

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]).

Constraints

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

Examples

Example 1

Input

graph = [[1,2],[3],[3],[]]

Output

[[0,1,3],[0,2,3]]

Example 2

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

Approaches

1. DFS backtracking with path tracking (canonical)

DFS from node 0. Push current node onto path; if at target n-1, record a copy of path; else recurse on each neighbor. Pop on backtrack.

Time: O(2^n * n) for path enumeration
Space: O(n) recursion + O(P * n) output where P is path count

function allPathsSourceTarget(graph) {
  const target = graph.length - 1;
  const out = [];
  function dfs(node, path) {
    path.push(node);
    if (node === target) out.push(path.slice());
    else for (const next of graph[node]) dfs(next, path);
    path.pop();
  }
  dfs(0, []);
  return out;
}

Tradeoff: Idiomatic backtracking. The path.slice() at the leaf is critical — push the snapshot, not the live array. Otherwise all output entries share the same mutating array.

2. BFS with explicit path copies

Use a queue of (node, path) pairs. Dequeue, extend by each neighbor, enqueue with the extended path.

Time: O(2^n * n)
Space: O(2^n * n)

function allPathsSourceTargetBFS(graph) {
  const target = graph.length - 1;
  const out = [];
  const queue = [[0, [0]]];
  while (queue.length) {
    const [node, path] = queue.shift();
    if (node === target) { out.push(path); continue; }
    for (const next of graph[node]) queue.push([next, [...path, next]]);
  }
  return out;
}

Tradeoff: Same asymptotic complexity but each enqueue allocates a new array — bad for cache. DFS with backtracking is preferred.

LinkedIn-specific tips

LinkedIn interviewers want the backtracking version with the slice-on-leaf insight. State explicitly: 'I'll push onto a shared path array, snapshot at the leaf, pop on backtrack — that avoids allocating a new array per edge expansion.' Be ready for: 'What if the graph could have cycles?' (Then you'd need a visited set per path, and the algorithm extends naturally — but the problem guarantees DAG.)

Common mistakes

Pushing `path` directly to out instead of `path.slice()` — all entries end up pointing to the same array (which is empty at the end).
Forgetting to pop on backtrack — corrupts the shared path for sibling branches.
Adding a visited set when the graph is a DAG — unnecessary overhead.

Follow-up questions

An interviewer at LinkedIn may pivot to one of these next:

What if you needed only the SHORTEST path? (BFS instead of full DFS.)
What if the graph had weights? (Path enumeration is fine; for shortest weighted use Dijkstra.)
What if you needed only the path COUNT (not the paths)? (Memo on `paths(node)` becomes O(n + edges).)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why doesn't this need visited tracking?

Because the graph is a DAG — no cycles. Without cycles, you can't loop back, so visited is implicit. If cycles were possible, you'd need a visited set per path (or accept potential infinite loops).

Could you use memoization for speedup?

Not for path enumeration — the number of paths can be exponential, so any caching of 'paths from node X' uses exponential memory. For PATH COUNT (not enumeration), memo on count(node) is O(n + edges).

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill All Paths From Source to Target and other LinkedIn interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →