Faangprep Logo
LoginRegister
Depth-First Search
Medium

Path Sum II

Find all root-to-leaf paths where each path's sum equals the targetSum.
10 min read
Solve on LeetCode
Examples
Input:root = [5,4,8,11,null,13,4,7,2,5,1], targetSum = 22
Output:[[5,4,11,2],[5,8,4,5]]
Explain:

Two paths sum to 22.

Problem Understanding

Unlike Path Sum I, we need to return all distinct paths that satisfy the condition, not just a boolean.

Since we need to store the actual path (list of nodes), we'll need to maintain a current_path list as we traverse. When we hit a valid leaf, we add a copy of current_path to our global result.

Algorithm Strategy (Backtracking)

We use DFS with Backtracking.

  1. State: Maintain current_path list and remaining_sum.
  2. Action: On visiting node, add node.val to current_path.
  3. Check: If leaf & node.val == remaining_sum, save a copy of the path.
  4. Recurse: Call left and right children.
  5. Backtrack: Crucially, pop the last element (node.val) from current_path before returning to parent. This cleans up the state for other branches.
Interactive Visualization
Step 1 / 21
5
curr
4
8
11
13
4
7
2
5
1
5
0
4
1
8
2
11
3
4
13
5
4
6
7
7
2
8
5
9
1
10

Visit 5. Path: [5]. Remaining needed: 17.

1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep