113. Path Sum II

(原本这个帖子是我录制的gas station数学证明的视频，但是我发帖后又后悔了><等准备好了再发出来吧~换了一个新的内容，幸好有库存😆)
It's similar with 257.Binary Tree Paths https://leetcode.com/problems/binary-tree-paths/description/ and 46. Permutations https://leetcode.com/problems/permutations/
The point is to "take photo" on qualified paths before it's changing. You want to record the correct `path`. I have two ways. They differs in when to "take the photo". Other than that it's all the same. 1 is easier to understand than 2, but with more expansive space cost.

**Solution 1**

When calling the recursive function, simply create new list to make it seperate with the other paths, otherwise the list will be overwritten when return back.
It's like you create parallel universes so that they don't bother each other. It's expensive in space complexity though.
```
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> output = new ArrayList<>();
        helper(root, sum, list, output);
        return output;
    }

    public void helper(TreeNode node, int sum, List<Integer> list, List<List<Integer>> output) {
        if (node == null) return;
        list.add(node.val);
        if (sum == node.val && node.left == null && node.right == null) {
            output.add(list);
        } else {
            sum -= node.val;
            helper(node.left, sum, new ArrayList(list), output); // Take "photo" here
            helper(node.right, sum, new ArrayList(list), output); // Take "photo" here
        }
    }
}
```


**Solution 2. Backtracking**

We can "take photo" once we found a qualified path. In this way, we don't have to cost that much on space because of creating "parallel universes". However, in this way, there's bug since we are not able to recover `path` after recursion. Because after each recursion, we have already `list.add(node.val);` before returning to a last level above.

Therefore, when we arriving at the last level above, the length of the list has increased 1. Therefore, we need to delete it to "recover" like we never touch before.
```
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> output = new ArrayList<>();
        helper(root, sum, list, output);
        return output;
    }

    private void helper(TreeNode node, int sum, List<Integer> list, List<List<Integer>> output) {
        if (node == null) return;
        list.add(node.val);
        if (sum == node.val && node.left == null && node.right == null) {
            output.add(new ArrayList(list)); // Take "photo" here
        } else {
            sum -= node.val;
            helper(node.left, sum, list, output);
            helper(node.right, sum, list, output);
        }
        list.remove(list.size() - 1); // Recover like you never touch it before
    }
}
```