> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0437-path-sum-iii.md).

# 0437. Path Sum III

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

## Description

Given the `root` of a binary tree and an integer `targetSum`, return *the number of paths where the sum of the values along the path equals* `targetSum`.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/04/09/pathsum3-1-tree.jpg)

```
**Input:** root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
**Output:** 3
**Explanation:** The paths that sum to 8 are shown.
```

**Example 2:**

```
**Input:** root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
**Output:** 3
```

**Constraints:**

* The number of nodes in the tree is in the range `[0, 1000]`.
* `-109 <= Node.val <= 109`
* `-1000 <= targetSum <= 1000`

## ac1: backtracking + prefix sum

```java
class Solution {
    int num;
    Map<Integer, Integer> map;

    public int pathSum(TreeNode root, int targetSum) {
        num = 0;
        map = new HashMap<>();
        // Important initiation: when prefixSum == targetSum.
        map.put(0, 1);

        process(root, 0, targetSum);

        return num;
    }

    private void process(TreeNode node, int prefixSum, int targetSum) {
        if (node == null) return;

        prefixSum += node.val;
        num += map.getOrDefault(prefixSum - targetSum, 0);

        map.put(prefixSum, map.getOrDefault(prefixSum, 0) + 1);

        process(node.left, prefixSum, targetSum);
        process(node.right, prefixSum, targetSum);

        map.put(prefixSum, map.getOrDefault(prefixSum, 0) - 1);
    }
}

// Backtracking for tree traversal + prefixSum to calculate sub-path sum.
```