# 0113. Path Sum II
###### tags: `Leetcode` `Medium` `FaceBook` `Backtracking`
Link: https://leetcode.com/problems/path-sum-ii/
## 思路 O(N^2) O(N)
**注意所有backtracking时间复杂度的分析**
这里不涉及到剪枝 因为每个node的val不一定都是正数
要注意题目有一个限定条件是结束的点必须是leaf node

时间复杂度：假设这个tree一共有N个node， 那么worst case leaf node就会有N/2个，那么就会有N/2个路径要尝试，每条路径的时间复杂度是O(N)(其实应该是tree的高度，但是因为不是balance tree，所以高度不能用logN表示)，因此时间复杂度是O(N^2)

空间复杂度：如果不考虑output的空间复杂度，是O(N) 因为用了curr list记录现在路径上有的node
## Code

class Solution {
    List<List<Integer>> ans;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        ans = new ArrayList<>();
        if(root == null) return ans;
        List<Integer> curr = new ArrayList<>();
        curr.add(root.val);
        backtracking(root, targetSum, curr, root.val);
        return ans;
    }
    public void backtracking(TreeNode root, int target, List<Integer> curr, int currSum){
        if(currSum==target && root.left==null && root.right==null){
            ans.add(new ArrayList<>(curr));
            return;
        }
        if(root.left!=null){
            curr.add(root.left.val);
            backtracking(root.left, target, curr, currSum+root.left.val);
            curr.remove(curr.size()-1);
        }
        if(root.right!=null){
            curr.add(root.right.val);
            backtracking(root.right, target, curr, currSum+root.right.val);
            curr.remove(curr.size()-1);
        }
    }
}