# LeetCode: Path Sum III Solution

If timebox exceeded, read other solutions

## Approach

Prefix sum is equivalent to accumulated sum

Final result is the sum of

• prefixSum === targetSum
: the current path sum is equal to target sum
• prefixSumCount[prefixSum - targetSum]
: number of sub-paths, each of whose is equal to target sum

## Implementation

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}var pathSum = function (root, targetSum) {2  const prefixSumCount = {}3  let res = 04
5  const recursion = (node, prefixSum) => {6    if (!node) return7
8    prefixSum += node.val9
10    res +=11      (prefixSum === targetSum) + (prefixSumCount[prefixSum - targetSum] || 0)12
13    if (!prefixSumCount[prefixSum]) prefixSumCount[prefixSum] = 014
15    prefixSumCount[prefixSum]++16    recursion(node.left, prefixSum)17    recursion(node.right, prefixSum)18    prefixSumCount[prefixSum]--19  }20
21  recursion(root, 0)22
23  return res24}```

Original problem

## Similar problems

Path Sum

Path Sum II

Path Sum IV

Longest Univalue Path

leetcode

tree

binary tree

dfs

recursion

## Next Post

LeetCode: Path Sum

Sep 10, 2022

Keep subtracting

## Previous Post

LeetCode: Kth Smallest Element in a BST

Sep 6, 2022

Inorder traversal

Search Posts