# 0113. 路径总和 II

### 题目地址(113. 路径总和 II)

<https://leetcode-cn.com/problems/path-sum-ii/>

### 题目描述

```
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

```

### 前置知识

* 回溯法

### 公司

* 阿里
* 腾讯
* 百度
* 字节

### 思路

这道题目是求集合，并不是`求值`，而是枚举所有可能，因此动态规划不是特别切合，因此我们需要考虑别的方法。

这种题目其实有一个通用的解法，就是回溯法。网上也有大神给出了这种回溯法解题的[通用写法](https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-\(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning\))，这里的所有的解法使用通用方法解答。 除了这道题目还有很多其他题目可以用这种通用解法，具体的题目见后方相关题目部分。

我们先来看下通用解法的解题思路，我画了一张图：

![](https://p.ipic.vip/m71dgr.jpg)

> 图是 [78.subsets](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/78.subsets)，都差不多，仅做参考。

通用写法的具体代码见下方代码区。

### 关键点解析

* 回溯法
* backtrack 解题公式

### 代码

* 语言支持：JS，C++，Python3

JavaScript Code：

```js
/*
 * @lc app=leetcode id=113 lang=javascript
 *
 * [113] Path Sum II
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
function backtrack(root, sum, res, tempList) {
  if (root === null) return;
  if (root.left === null && root.right === null && sum === root.val)
    return res.push([...tempList, root.val]);

  tempList.push(root.val);
  backtrack(root.left, sum - root.val, res, tempList);

  backtrack(root.right, sum - root.val, res, tempList);
  tempList.pop();
}
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function (root, sum) {
  if (root === null) return [];
  const res = [];
  backtrack(root, sum, res, []);
  return res;
};
```

C++ Code:

```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        auto ret = vector<vector<int>>();
        auto temp = vector<int>();
        backtrack(root, sum, ret, temp);
        return ret;
    }
private:
    void backtrack(const TreeNode* root, int sum, vector<vector<int>>& ret, vector<int>& tempList) {
        if (root == nullptr) return;
        tempList.push_back(root->val);
        if (root->val == sum && root->left == nullptr && root->right == nullptr) {
            ret.push_back(tempList);
        } else {
            backtrack(root->left, sum - root->val, ret, tempList);
            backtrack(root->right, sum - root->val, ret, tempList);
        }
        tempList.pop_back();
    }
};
```

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        if not root:
            return []

        result = []

        def trace_node(pre_list, left_sum, node):
            new_list = pre_list.copy()
            new_list.append(node.val)
            if not node.left and not node.right:
                # 这个判断可以和上面的合并，但分开写会快几毫秒，可以省去一些不必要的判断
                if left_sum == node.val:
                    result.append(new_list)
            else:
                if node.left:
                    trace_node(new_list, left_sum-node.val, node.left)
                if node.right:
                    trace_node(new_list, left_sum-node.val, node.right)

        trace_node([], sum, root)
        return result
```

### 相关题目

* [39.combination-sum](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/39.combination-sum)
* [40.combination-sum-ii](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/40.combination-sum-ii)
* [46.permutations](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/46.permutations)
* [47.permutations-ii](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/47.permutations-ii)
* [78.subsets](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/78.subsets)
* [90.subsets-ii](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/90.subsets-ii)
* [131.palindrome-partitioning](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/131.palindrome-partitioning)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/113.path-sum-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.