Link: https://leetcode.com/problems/path-sum-iii/
Solution:
Topics: DFS, back tracking, Path sum II, Subarray sum equals k
Intuition
This is a great problem that combines the classic path sum problems with the classic Subarray sum equals k. Basically the idea is to traverse the tree with a DFS while maintaining a hash map of the sums in the current path.
Also, instead of maintaining a separate copy of the hash-map for every path, we can simply use backtracking to use a single global hash map. This is possible because in a DFS, after a path has been terminated, it pops itself off in reverse order of the path, so we can just clean the hash map in post-order.
Implementation
Visual
Same as Path sum II
Review 1
Fun problem! Not much to add.