# 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

1var pathSum = function (root, targetSum) {2 const prefixSumCount = {}3 let res = 045 const recursion = (node, prefixSum) => {6 if (!node) return78 prefixSum += node.val910 res +=11 (prefixSum === targetSum) + (prefixSumCount[prefixSum - targetSum] || 0)1213 if (!prefixSumCount[prefixSum]) prefixSumCount[prefixSum] = 01415 prefixSumCount[prefixSum]++16 recursion(node.left, prefixSum)17 recursion(node.right, prefixSum)18 prefixSumCount[prefixSum]--19 }2021 recursion(root, 0)2223 return res24}

## References

## Similar problems

Path Sum II

Path Sum IV

Longest Univalue Path

## Comments

Loading comments...

## Tags

leetcode

tree

binary tree

dfs

recursion

## Apply and earn a $2,500 bonus once you're hired on your first job!

Clients from the Fortune 500 to Silicon Valley startups

Choose your own rate, get paid on time

From hourly, part-time, to full-time positions

Flexible remote working environment

A lot of open JavaScript jobs!!

**Fact corner:** Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.

**Still hesitate?** Read HoningJS author's guide on dealing with Toptal interview process.