Path Sum II - Solution & Explanation

Using a recursive DFS, traverse each path from root to leaf, maintaining the current path and its corresponding sum. When a leaf is reached, check if the path's sum matches the targetSum. Use backtracking to explore all paths.

We use a helper function, dfs, to recursively explore paths. We store current paths and their sums in arrays to keep track of potential solutions. When a solution is found at a leaf node, it is added to the result set, and backtracking ensures all paths are checked.

An iterative approach using a stack can also be used for this problem. We maintain stacks that parallel traditional DFS traversal with added structures to track path and cumulative sum states for efficient exploration of all feasible root-to-leaf paths.

This C++ solution employs a stack to simulate DFS traversal iteratively. The stack holds node, cumulative sum, and path data. As each node is processed, we check for valid paths and update the result list accordingly. Paths are extended by exploring left and right children, augmented by the current node value.