# 113. Path Sum II

[Link](https://leetcode.com/problems/path-sum-ii/)

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

**Note:** A leaf is a node with no children.

**Example:**

Given the below binary tree and `sum = 22`,

```
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1
```

Return:

```
[
   [5,4,11,2],
   [5,8,4,5]
]
```

**Solution**

標準的backtracking列舉所有可能性

```
  public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> ret = new LinkedList<>();
        if(root == null) return ret;
        helper(root, new LinkedList<Integer>(), ret, sum);
        return ret;
    }
    
    public void helper(TreeNode node, List<Integer> temp, List<List<Integer>> finalRet, int sum){
        if(node.right == null && node.left == null && node.val == sum){
            temp.add(node.val);
            finalRet.add(new ArrayList<>(temp));
            temp.remove(temp.size()-1);
        }
        if(node.right != null){
            temp.add(node.val);
            helper(node.right, temp, finalRet, sum-node.val);
            temp.remove(temp.size()-1);
        }
        if(node.left != null){
            temp.add(node.val);
            helper(node.left, temp, finalRet, sum-node.val);
            temp.remove(temp.size()-1);
        }
    }
```
