How do you solve All Paths From Source to Target on LeetCode?

All Paths From Source to Target (LeetCode #797) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Understanding the structure of a DAG helps in efficiently exploring paths.

What is the brute force solution for All Paths From Source to Target?

The brute force approach for All Paths From Source to Target is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach explores all possible paths from the source node to the target node. This is done by recursively visiting each node and backtracking when we reach the target or a dead end. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for All Paths From Source to Target?

Clearly explain your thought process while coding. Consider edge cases and discuss them with the interviewer. Practice writing recursive functions, as they are common in graph problems.

What are common mistakes when solving All Paths From Source to Target?

Forgetting to backtrack properly, which can lead to incorrect paths being stored. Not handling edge cases, such as when there are no paths available.

#797

All Paths From Source to Target

Medium

BacktrackingDepth-First SearchBreadth-First SearchGraph TheoryBacktrackingDepth-First Search

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses Depth-First Search (DFS) to explore paths efficiently while maintaining a list of paths. This approach leverages the properties of the directed acyclic graph (DAG) to avoid redundant calculations.

⚙️

Algorithm

4 steps

1Step 1: Initialize a result list to store all paths.
2Step 2: Use a recursive DFS function to explore paths from the current node.
3Step 3: When the target node is reached, add the current path to the result list.
4Step 4: Backtrack to explore other potential paths.

solution.py12 lines

1def allPathsSourceTarget(graph):
2    def dfs(node, path):
3        if node == len(graph) - 1:
4            result.append(path[:])
5            return
6        for neighbor in graph[node]:
7            path.append(neighbor)
8            dfs(neighbor, path)
9            path.pop()
10    result = []
11    dfs(0, [0])
12    return result

ℹ

Complexity note: The time complexity is O(n) because each node and edge is processed once. The space complexity is O(n) due to the recursion stack and the storage of paths.

1Understanding the structure of a DAG helps in efficiently exploring paths.
2Backtracking is a powerful technique for exploring all possible paths.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.