Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target. A valid path is from root node to any of the leaf nodes.

Example
Example 1:
Input:
{1,2,4,2,3}
5
Output: [[1, 2, 2],[1, 4]]
Explanation:
The tree is look like this:
         1
        / \
       2   4
      / \
     2   3
For sum = 5 , it is obviously 1 + 2 + 2 = 1 + 4 = 5
Example 2:
Input:
{1,2,4,2,3}
3
Output: []
Explanation:
The tree is look like this:
         1
        / \
       2   4
      / \
     2   3
Notice we need to find all paths from root node to leaf nodes.
1 + 2 + 2 = 5, 1 + 2 + 3 = 6, 1 + 4 = 5 
There is no one satisfying it.

Method 1. 类似permutation的recursion

public class Solution {
    /*
     * @param root: the root of binary tree
     * @param target: An integer
     * @return: all valid paths
     */
    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        // write your code here
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> clist = new ArrayList<>();
        if(root == null) return res;
        helper(root, target, res, clist);
        return res;
    }

    private void helper(TreeNode root, int target, List<List<Integer>> res, List<Integer> clist) {
        if(root.left == null && root.right == null && target - root.val == 0) {
            List<Integer> temp = new ArrayList<>();
            temp.addAll(clist);
            temp.add(root.val);
            res.add(temp);
        }

        clist.add(root.val);
        if(root.left != null) {
            helper(root.left, target - root.val, res, clist);
        }
        if(root.right != null) {
            helper(root.right, target - root.val, res, clist);
        }
        clist.remove(clist.size() - 1);
    }
}

下面是优化一下的版本，在clist remove最后一个前就判断放不放res里面
public class Solution { 
    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> clist = new ArrayList<>();
        if(root == null) return res;
        helper(root, target, res, clist);
        return res;
    }

    private void helper(TreeNode root, int target, List<List<Integer>> res, List<Integer> clist) {
        clist.add(root.val);
        if(root.left != null) {
            helper(root.left, target - root.val, res, clist);
        }
        if(root.right != null) {
            helper(root.right, target - root.val, res, clist);
        }

        if(root.left == null && root.right == null && target - root.val == 0) {
            res.add(new ArrayList(clist));
        }
        clist.remove(clist.size() - 1);
    }
}


Method 2. divide and conquer