/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, sum int) (cnt int) {
	helper(root, []*TreeNode{}, sum, 0, &cnt)
	return
}

func helper(node *TreeNode, path []*TreeNode, sum, currSum int, cnt *int) {
	if node == nil {
		return
	}
	currSum += node.Val
	if currSum == sum {
		(*cnt)++
	}
	n := len(path)
	for cs, i := currSum, 0; i < n; i++ {
		cs -= path[i].Val
		if cs == sum {
			(*cnt)++
		}
	}
	helper(node.Left, append(path, node), sum, currSum, cnt)
	helper(node.Right, append(path, node), sum, currSum, cnt)
}