# Path Sum II Leetcode Solution

In this post, we are going to solve the Path Sum II Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

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

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.

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`

Now, lets see the leetcode solution of Path Sum II Leetcode Solution.

### Path Sum II Leetcode Solution in Python

```class Solution:
def pathSum(self, root: TreeNode, summ: int) -> List[List[int]]:
ans = []

def dfs(root: TreeNode, summ: int, path: List[int]) -> None:
if not root:
return
if root.val == summ and not root.left and not root.right:
ans.append(path + [root.val])
return

dfs(root.left, summ - root.val, path + [root.val])
dfs(root.right, summ - root.val, path + [root.val])

dfs(root, summ, [])
return ans```

### Path Sum IILeetcode Solutionin CPP

```class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> ans;
dfs(root, sum, {}, ans);
return ans;
}

private:
void dfs(TreeNode* root, int sum, vector<int>&& path,
vector<vector<int>>& ans) {
if (root == nullptr)
return;
if (root->val == sum && root->left == nullptr && root->right == nullptr) {
path.push_back(root->val);
ans.push_back(path);
path.pop_back();
return;
}

path.push_back(root->val);
dfs(root->left, sum - root->val, move(path), ans);
dfs(root->right, sum - root->val, move(path), ans);
path.pop_back();
}
};```

### Path Sum II Leetcode Solution in Java

```class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> ans = new ArrayList<>();
dfs(root, sum, new ArrayList<>(), ans);
return ans;
}

private void dfs(TreeNode root, int sum, List<Integer> path, List<List<Integer>> ans) {
if (root == null)
return;
if (root.val == sum && root.left == null && root.right == null) {
path.remove(path.size() - 1);
return;
}