  # LeetCode - Path Sum II

## Problem statement

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 values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Problem statement taken from: https://leetcode.com/problems/path-sum-ii

Example 1: ``````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
``````

Example 2: ``````Input: root = [1, 2, 3], targetSum = 5
Output: []
``````

Example 3:

``````Input: root = [1, 2], targetSum = 0
Output: []
``````

Constraints:

``````- The number of nodes in the tree is in the range [0, 5000]
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
``````

### Explanation

The problem is similar to our previous blog post Path Sum. We will use the same algorithm flow here, but we will also store the tree node values in an array.

Let's check the algorithm first.

``````- set 2D array vector<vector<int>> result
1D array vector<int> current

- getPathSum(root, result, current, targetSum)

- return result

// getPathSum function
- if root == NULL
- return

- if root->val == targetSum && root->left == NULL && root->right == NULL
- current.push_back(root->val)
- result.push_back(current)
- return

- set remainingTargetSum = targetSum - root->val
- current.push_back(root->val)

- getPathSum(root->left, result, current, remainingTargetSum)
- getPathSum(root->right, result, current, remainingTargetSum)

- return
``````

Let's check our algorithm in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
void getPathSum(TreeNode* root, vector<vector<int>> &result, vector<int> current, int targetSum) {
if(root == NULL) {
return;
}

if(root->val == targetSum && root->left == NULL && root->right == NULL) {
current.push_back(root->val);
result.push_back(current);
return;
}

int remainingTargetSum = targetSum - root->val;
current.push_back(root->val);

getPathSum(root->left, result, current, remainingTargetSum);
getPathSum(root->right, result, current, remainingTargetSum);

return;
}

vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> result;
vector<int> current;

getPathSum(root, result, current, targetSum);

return result;
}
};``````

#### Golang solution

``````func getPathSum(root *TreeNode, result *[][]int, current []int, targetSum int) {
if root == nil {
return
}

if root.Val == targetSum && root.Left == nil && root.Right == nil {
current = append(current, root.Val)
*result = append(*result, append([]int(nil),current...))
return
}

remainingTargetSum := targetSum - root.Val

current = append(current, root.Val)

getPathSum(root.Left, result, current, remainingTargetSum)
getPathSum(root.Right, result, current, remainingTargetSum)

return
}

func pathSum(root *TreeNode, targetSum int) [][]int {
result := [][]int{}
current := []int{}

getPathSum(root, &result, current, targetSum)

return result
}``````

#### Javascript solution

``````var pathSum = function(root, targetSum) {
let result = [];

var getPathSum = function(root, current, targetSum) {
if(root === null) {
return;
}

if(root.val === targetSum && root.left === null && root.right === null) {
result.push([...current, root.val]);
return;
}

let remainingTargetSum = targetSum - root.val;

getPathSum(root.left, [...current, root.val], remainingTargetSum);
getPathSum(root.right, [...current, root.val], remainingTargetSum);

return;
}

getPathSum(root, [], targetSum);

return result;
};``````

#### Dry Run

Let's dry-run our algorithm for Example 1.

``````Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]
targetSum = 22

Step 1: initialize vector<vector<int>> result;
vector<int> current;

Step 2: getPathSum(root, result, current, targetSum)
getPathSum(root, [[]], [], 22)
the root is at 5

// getPathSum
Step 3: if root == NULL
false

if root->val == targetSum && root->left == NULL && root->right == NULL
5 == 22
false

remainingTargetSum = targetSum - root->val
= 22 - 5
= 17

current.push_back(root->val)
current = 

getPathSum(root->left, result, current, remainingTargetSum)
getPathSum(4, [[]], , 17)

Step 4: if root == NULL
the root is at 4
false

if root->val == targetSum && root->left == NULL && root->right == NULL
4 == 17
false

remainingTargetSum = targetSum - root->val
= 17 - 4
= 13

current.push_back(root->val)
current = [5, 4]

getPathSum(root->left, result, current, remainingTargetSum)
getPathSum(11, [[]], [5, 4], 13)

Step 5: if root == NULL
the root is at 11
false

if root->val == targetSum && root->left == NULL && root->right == NULL
11 == 13
false

remainingTargetSum = targetSum - root->val
= 13 - 11
= 2

current.push_back(root->val)
current = [5, 4, 11]

getPathSum(root->left, result, current, remainingTargetSum)
getPathSum(7, [[]], [5, 4, 11], 2)

Step 6: if root == NULL
the root is at 7
false

if root->val == targetSum && root->left == NULL && root->right == NULL
7 == 2
false

remainingTargetSum = targetSum - root->val
= 2 - 7
= -5

current.push_back(root->val)
current = [5, 4, 11, 7]

getPathSum(root->left, result, current, remainingTargetSum)
getPathSum(NULL, [[]], [5, 4, 11, 7], -5)

Step 7: if root == NULL
the root is NULL
true

We backtrack to step 6 and continue

Step 8: getPathSum(root->right, result, current, remainingTargetSum)
getPathSum(2, [[]], [5, 4, 11], 2)

Step 9: if root == NULL
the root is at 2
false

if root->val == targetSum && root->left == NULL && root->right == NULL
2 == 2 && root->left == NULL && root->right == NULL
true

current.push_back(root->val)
current = [5, 4, 11, 2]

result.push_back(current)
result = [[5, 4, 11, 2]]

return

We backtrack to step 4 and continue

Step 10: getPathSum(root->right, result, current, remainingTargetSum)
getPathSum(NULL, [[5, 4, 11, 2]], [5, 4], 13)

Step 11: if root == NULL
the root is NULL
true

We backtrack to step 3 and continue

Step 12: getPathSum(root->right, result, current, remainingTargetSum)
getPathSum(8, [[5, 4, 11, 2]], , 17)

Step 13: if root == NULL
the root is at 8
false

if root->val == targetSum && root->left == NULL && root->right == NULL
8 == 17
false

remainingTargetSum = targetSum - root->val
= 17 - 8
= 9

current.push_back(root->val)
current = [5, 8]

getPathSum(root->left, result, current, remainingTargetSum)
getPathSum(13, [[5, 4, 11, 2]], [5, 8], 9)

Step 14: if root == NULL
the root is at 13
false

if root->val == targetSum && root->left == NULL && root->right == NULL
13 == 9
false

remainingTargetSum = targetSum - root->val
= 9 - 13
= -4

current.push_back(root->val)
current = [5, 8, 13]

getPathSum(root->left, result, current, remainingTargetSum)
getPathSum(NULL, [[5, 4, 11, 2]], [5, 8, 13], -4)

Step 15: if root == NULL
the root is NULL
true

We backtrack to step 14 and continue

Step 16: getPathSum(root->right, result, current, remainingTargetSum)
getPathSum(NULL, [[5, 4, 11, 2]], [5, 8, 13], -4)

Step 17: if root == NULL
the root is NULL
true

We backtrack to step 13 and continue

Step 18: getPathSum(root->right, result, current, remainingTargetSum)
getPathSum(4, [[5, 4, 11, 2]], [5, 8], 9)

Step 19: if root == NULL
the root is at 4
false

if root->val == targetSum && root->left == NULL && root->right == NULL
4 == 9
false

remainingTargetSum = targetSum - root->val
= 9 - 4
= 5

current.push_back(root->val)
current = [5, 8, 4]

getPathSum(root->left, result, current, remainingTargetSum)
getPathSum(5, [[5, 4, 11, 2]], [5, 8, 4], 5)

Step 20: if root == NULL
the root is at 5
false

if root->val == targetSum && root->left == NULL && root->right == NULL
5 == 5
true

current.push_back(root->val)
current = [5, 8, 4, 5]

result.push_back(current)
result = [[5, 4, 11, 2], [5, 8, 4, 5]]

return

We backtrack to step 19 and continue

Once the last rightmost lead node is processed
we return the result

The answer is [[5, 4, 11, 2], [5, 8, 4, 5]].
``````