# LeetCode: 113. Path Sum II

**The Problem**

Given the `root`

of a binary tree and an integer `targetSum`

, return *all root-to-leaf paths where the sum of the node values in the path equals *

`targetSum`

*. Each path should be returned as a list of the node*.

**, not node references****values**A ** root-to-leaf** path is a path starting from the root and ending at any leaf node. A

**is a node with no children.**

**leaf****Example**

```
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
```

**Constraints:**

- The number of nodes in the tree is in the range
`[0, 5000]`

. `-1000 <= Node.val <= 1000`

`-1000 <= targetSum <= 1000`

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

```
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> ans;
vector<int> t;
pathSumHelper( root, t, ans, targetSum, 0 );
return ans;
}
void pathSumHelper( TreeNode *&root,
vector<int> &vec, vector<vector<int>> &ans,
int &targetSum, int currentSum
) {
if (root == NULL) return;
int newSum = currentSum + root->val;
vec.push_back(root->val);
if( root->left == NULL && root->right == NULL ) {
if( newSum == targetSum ) ans.push_back(vec);
vec.pop_back();
return;
} else {
if(root->left != NULL)
pathSumHelper(root->left, vec, ans, targetSum, newSum);
if(root->right != NULL)
pathSumHelper(root->right, vec, ans, targetSum, newSum);
}
vec.pop_back();
}
```

Here's a step-by-step explanation of the code:

1. `vector<vector<int>> pathSum(TreeNode* root, int targetSum)`

: This is the main function that you call to find all paths in the binary tree. It takes the root of the tree and the target sum as input and returns a 2D vector (`vector<vector<int>>`

) containing all the paths.

2. Inside the `pathSum`

function:

`vector<vector<int>> ans;`

: This vector will store the final result, i.e., all paths that match the target sum.`vector<int> currentPath;`

: This is an empty vector used to temporarily store a path as it's being traversed.`pathSumHelper(root, currentPath, ans, targetSum, 0);`

: It calls the helper function`pathSumHelper`

to start the DFS traversal of the tree.

3. `void pathSumHelper(TreeNode *&root, vector<int> ¤tPath, vector<vector<int>> &ans, int &targetSum, int currentSum)`

: This is the helper function that performs the DFS traversal and path sum calculation.

`TreeNode *&root`

: A reference to the current node being processed.`vector<int> ¤tPath`

: A reference to the vector used to store the current path.`vector<vector<int>> &ans`

: A reference to the vector that stores the final result.`int &targetSum`

: A reference to the target sum.`int currentSum`

: The sum of values along the current path.

4. Inside the `pathSumHelper`

function:

`if (root == NULL) return;`

: If the current node is`NULL`

, it means the end of the path has been reached, so it returns.`int newSum = currentSum + root->val;`

: Calculates the new sum by adding the current node's value to the sum of values along the path.`currentPath.push_back(root->val);`

: Adds the current node's value to the path being constructed.`if (root->left == NULL && root->right == NULL)`

: Checks if the current node is a leaf node (i.e., it has no left or right children).- If the current sum equals the target sum (
`newSum == targetSum`

), it means a valid path has been found, so it adds the path (stored in`currentPath`

) to the`ans`

vector. - Then, it removes the last element from
`currentPath`

using`currenPath.pop_back()`

to backtrack. - If the current node is not a leaf node, it recursively calls
`pathSumHelper`

on its left and right children, passing the updated`currentPath`

and`newSum`

.

5. Finally, after the traversal is complete, the `pathSum`

function returns the `ans`

vector, which contains all the paths in the tree that match the target sum.