437. Path Sum III

class Solution {
public:
    int pathSum(TreeNode *root, int targetSum) {
        int possible_cases = 0;
        // Note: the initial pair {0, 1} is required.
        // It represents an empty prefix sum before the root.
        // For example, when target_sum == 5 and root->val == 5,
        // current_sum - target_sum == 0, and this allows the path
        // starting from the root to be counted correctly.
        unordered_map<long long, int> path_sum_count{{0, 1}};

        count_path_sum(root, targetSum, 0, possible_cases, path_sum_count);

        return possible_cases;
    }

private:
    void count_path_sum(
        TreeNode *root,
        int target_sum,
        long long current_sum,
        int &possible_cases,
        unordered_map<long long, int> &path_sum_count) {
        if (root != nullptr) {
            current_sum += root->val;

            // The path does not have to start from the root.
            // Let prefix_sum be the sum before the current node, and total_sum be the sum up to the
            // current node. If total_sum - prefix_sum == target_sum, then the path between them
            // forms a valid answer. Therefore, we count how many times (total_sum - target_sum) has
            // appeared as a prefix sum.
            possible_cases += path_sum_count[current_sum - target_sum];
            ++path_sum_count[current_sum];

            count_path_sum(root->left, target_sum, current_sum, possible_cases, path_sum_count);
            count_path_sum(root->right, target_sum, current_sum, possible_cases, path_sum_count);

            --path_sum_count[current_sum];
        }
    }
};