package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, sum int) [][]int {
	result := make([][]int, 0)
	path := make([]int, 0)
	pathSumHelper(&result, &path, root, sum)
	return result
}

func pathSumHelper(result *[][]int, path *[]int, root *TreeNode, sum int) {
	if root == nil {
		return
	}
	*path = append(*path, root.Val)
	if root.Left == nil && root.Right == nil && root.Val == sum {
		newPath := make([]int, len(*path)) // Deep copy & pointer
		copy(newPath, *path)               // Important!!!
		*result = append(*result, newPath)
	}
	pathSumHelper(result, path, root.Left, sum-root.Val)
	pathSumHelper(result, path, root.Right, sum-root.Val)
	*path = (*path)[:len(*path)-1]
}

// func main() {
// 	//         3
// 	//        / \
// 	//       7  -1
// 	//      /\   /\
// 	//     1  5 9  4
// 	root1 := sortedArrayToBST([]int{1, 7, 5, 3, 9, -1, 4})
// 	fmt.Println(pathSum(root1, 11))
// 	fmt.Println(pathSum(root1, 12))
// }