**Solution**

**Path Sum II** https://leetcode.com/problems/path-sum-ii/

- When do we have a valid path? When root is a leaf and root,val == sum.
- Refer to https://leetcode.com/problems/path-sum/ to understand path sum constraints. Detailed solution is available at: https://discuss.leetcode.com/topic/72240/python-solution-with-detailed-explanation
- Refer to https://leetcode.com/problems/binary-tree-paths/ to understand the template to capture all paths. Detailed solution is available at: https://discuss.leetcode.com/topic/72244/python-solution-with-detailed-explanation
- Time complexity: O(N^2) - Use the same explanation provided in https://discuss.leetcode.com/topic/72244/python-solution-with-detailed-explanation

```
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
result = []
if root:
self.helper(root, [], result, sum)
return result
def helper(self, root, so_far, result, sum):
if root.left is None and root.right is None and root.val == sum:
so_far.append(root.val)
result.append([x for x in so_far])
so_far.pop()
else:
so_far.append(root.val)
if root.left:
self.helper(root.left, so_far, result, sum-root.val)
if root.right:
self.helper(root.right, so_far, result, sum-root.val)
so_far.pop()
return
```