# 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.

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.

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, letâ€™s 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;
}