# 113.M 路径总和 II

> Problem: [113. 路径总和 II](https://leetcode.cn/problems/path-sum-ii/description/)

## 思路

与上一题判断是否存路径总和为目标值的路径相比，差别在于需要用两个变量来存储路径。

* `paths`：路径集合，作为返回结果
* `path`：存储一条路径（`append`到`paths`时需要`深拷贝`）
* 每次递归完左右子树之后，需要回退当前节点。

## Code

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) [][]int {
	var paths [][]int
	var path []int
	helper(root, targetSum, path, &paths)
	return paths
}

func helper(root *TreeNode, targetSum int, path []int, paths *[][]int) {
	if root == nil {
		return
	}
	path = append(path, root.Val)
	targetSum -= root.Val
	if root.Left == nil && root.Right == nil && targetSum == 0 {
		// 注意这里需要深拷贝
		*paths = append(*paths, append([]int{}, path...))
	}

	helper(root.Left, targetSum, path, paths)
	helper(root.Right, targetSum, path, paths)
	// 回退当前节点
	path = path[0 : len(path)-1]
}
```