# 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]
]

## Analysis

Similar to Path Sum I, using DFS to find the path with a targeted sum, yet it requires additional space to store the intermediate results, thus creating helper function with temporal results argument.
One tricky part is to add root.val to the temporal results first and check if it matches targeted sum (passed in), if so remove it from temporal results, because the same temporal list will be used in a different branch as well

## Solution

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if (root == null) return paths;
pathSumHelper(root, sum, currentPath, paths);
return paths;
}
void pathSumHelper(TreeNode root, int sum, List<Integer> currentPath, List<List<Integer>> paths) {
if (root == null) return;
if (root.val == sum && root.left == null && root.right == null) {
// remember to remove the last element for upper level recursive call
currentPath.remove(currentPath.size() - 1);
return;
} else {
pathSumHelper(root.left, sum - root.val, currentPath, paths);
pathSumHelper(root.right, sum - root.val, currentPath, paths);
}
// remember to remove the last element for upper level recursive call
currentPath.remove(currentPath.size() - 1);
}
}
Simplify Back-tracking
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private List<List<Integer>> allValidPaths;
public List<List<Integer>> pathSum(TreeNode root, int sum) {
allValidPaths = new ArrayList<>();
traverse(root, sum, 0, new ArrayList<>());
return allValidPaths;
}
private void traverse(TreeNode node, int sum, int currSum, List<Integer> sumPath) {
if(node == null) return;
currSum += node.val;
if(node.left == null && node.right == null && currSum == sum) {
}
else {
traverse(node.left, sum, currSum, sumPath);
traverse(node.right, sum, currSum, sumPath);
}
sumPath.remove(sumPath.size()-1);
}
}
Simplify Helper Function
class Solution {
private List<List<Integer>> allValidPaths;
public List<List<Integer>> pathSum(TreeNode root, int sum) {
allValidPaths = new ArrayList<>();
traverse(root, sum, new ArrayList<>());
return allValidPaths;
}
private void traverse(TreeNode node, int sum, List<Integer> sumPath) {
if(node == null) return;