> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/binary-search-and-tree/113.-path-sum-ii.md).

# 113. Path Sum II

\# Medium

{% hint style="info" %}
Similar to #112.

Be carefull to operate list, the defaul copy is deep copy.
{% endhint %}

{% tabs %}
{% tab title="Python" %}

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        paths = []
        path = []
        
        if root == None:
            return paths
        
        self.pathRecord(root, sum, paths, path)
        return paths
    
    def pathRecord(self, root, sum, paths, path):
        # edge case
        path.append(root.val)
        path_o = path[:]

        if root.left == None and root.right == None:
            if root.val == sum:
                paths.append(path)
            return
        
        # regular case
        if root.left != None:
            self.pathRecord(root.left, sum-root.val, paths, path)
        if root.right != None:
            path = path_o[:]
            self.pathRecord(root.right, sum-root.val, paths, path)
            
```

{% endtab %}

{% tab title="Second Tab" %}

{% endtab %}
{% endtabs %}

Time complexity = $$O(n)$$ , space complexity = $$O(1)$$ . Because the worst case is to traversal all nodes and each node only bring one information `True` or `False`.