# Concise C++ prefix-sum solution with explanation

• There are two cases when target sum is zero and non-zero, both of them I handle within one line with no branching (read place: `ans += ...`).

`1.`: Non-zero sum case is trivial;

`2.`: Zero sum case is less trivial. Consider two subcases:

`2.1.`: Path: `2 3 -3`. Then prefix sums would be: `2 5 2`. So every time number repeats, it means we have zero sum subpath, so number of occurrences `- !tsum`;

`2.2.`: Path: `0 0 1`. Then prefix sums would be: `0 0 1`. Because I initialized `st` with `0`, we have `3` zeroes, then `- !tsum` fits here just fine as in `2.1.` case. Also initial `0` in `st` is also needed for non-zero case when subpath with target sum starting from root;

``````class Solution {
void dfs(TreeNode* r, multiset<int>& st, int& ans, int tsum, int sum)
{
if(!r) return;

vector<TreeNode*> ch = {r->left, r->right};

int __sum = sum + r->val;

st.insert(__sum);

ans += st.count(__sum - tsum) - !tsum;

for(auto nd : ch) dfs(nd, st, ans, tsum, __sum);

st.erase(st.find(__sum));
}

public:
int pathSum(TreeNode* root, int sum)
{
multiset<int> st = {0};
int ans = 0;

dfs(root, st, ans, sum, 0);

return ans;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.