[C++] Prefix Summ + DFS Solution Explained, ~99% Time, ~80% Space
I already solved this problem thrice, but I also forgot it I did and it was okay, since I went on for another run, outperforming all my previous attempts :)\n\n
I already solved this problem [thrice](https://leetcode.com/problems/path-sum-iii/discuss/779575/C%2B%2B-3-DFS-Based-Solutions-Explained-and-Compared-up-to-~100-Time-~75-Space), but I also forgot it I did and it was okay, since I went on for another run, outperforming all my previous attempts :)\n\nTo solve this problem, the approach we will be using here remains the same (a preoder DFS traversal) and what we change is where/how we store our data, leveraging the full power of a prefix sum.\n\nTo do so,  we will declare first of all a few class variables:\n* `sums` is an array of `1001` elements (the maximum we will have to store according to the specs and we will actually get a test cases with only right nodes for that size;\n* `pos` is the pointer to what cell of `sums` we are going to write in next, initially set to `0`, the first cell;\n* `t` is a copy of our `targetSum` variable, so not to have to pass it around all the time;\n* `res` is our accumulator variable and it will be increased by `1` for each match we will find, initially set to `0` too.\n\nIn our main function, we will first of all check if we have a single node to parse at all or not (and if not, just `return` `0`), then assign the correct value to `t` and call our `dfs` helper passing `root`.\n\nThis help takes a `TreeNode` pointer `root` as its solve parameter and:\n* extracts `root->val` and stores into `val`;\n* checks if that `val` itself is a match for our target (since single node paths are still valid) and in case increases `res` by `1`;\n* updates all the values currently stored in `sums` adding `val` to them and again checking if said values are matches, in case further increasing `res`;\n* adds the current value itself to `sums` and moves `pos` forward by one step;\n* checks if we have now any more `left` or `right` children and in case recurses to them;\n* finally, it backtracks our work on `sums`, reducing `pos` by `1` and subtracting `val` from each remaining value.\n\nOnce done, we will be back in our main function and we will just have to `return` `res` :)\n\nThe code:\n\n```cpp\nclass Solution {\n    int sums[1001], pos = 0, t, res = 0;\n    void dfs(TreeNode *root) {\n        // support variables\n        int val = root->val;\n        // checking if val alone matches t\n        if (val == t) res++;\n        // updating all the prefix sums and then the value itself at the end of it\n        for (int i = 0; i < pos; i++) {\n            sums[i] += val;\n            if (sums[i] == t) res++;\n        }\n        sums[pos++] = val;\n        if (root->left) dfs(root->left);\n        if (root->right) dfs(root->right);\n        // backtracking on the prefix sums\n        pos--;\n        for (int i = 0; i < pos; i++) sums[i] -= val;\n    }\npublic:\n    int pathSum(TreeNode *root, int targetSum) {\n        if (!root) return 0;\n        t = targetSum;\n        dfs(root);\n        return res;\n    }\n};\n```\n\nMicro-optimised version of `dfs` that does not bother backtracking when we are on the rightmost segment:\n\n```cpp\n    void dfs(TreeNode *root, bool isRight = true) {\n        // support variables\n        int val = root->val;\n        // checking if val alone matches t\n        if (val == t) res++;\n        // updating all the prefix sums and then the value itself at the end of it\n        for (int i = 0; i < pos; i++) {\n            sums[i] += val;\n            if (sums[i] == t) res++;\n        }\n        sums[pos++] = val;\n        if (root->left) dfs(root->left, false);\n        if (root->right) dfs(root->right, isRight);\n        // backtracking on the prefix sums\n        if (!isRight) {\n            pos--;\n            for (int i = 0; i < pos; i++) sums[i] -= val;\n        }\n    }\n```\n\nAnd even better, if we just keep track of the last node we saw while traversing - I actually manage to save memory and run a bit faster on average \uD83C\uDF89 :\n\n```cpp\n    void dfs(TreeNode *root, bool isLast = true) {\n        // support variables\n        int val = root->val;\n        // checking if val alone matches t\n        if (val == t) res++;\n        // updating all the prefix sums and then the value itself at the end of it\n        for (int i = 0; i < pos; i++) {\n            sums[i] += val;\n            if (sums[i] == t) res++;\n        }\n        sums[pos++] = val;\n        if (root->left) dfs(root->left, isLast && !root->right);\n        if (root->right) dfs(root->right, isLast);\n        // backtracking on the prefix sums\n        if (!isLast) {\n            pos--;\n            for (int i = 0; i < pos; i++) sums[i] -= val;\n        }\n    }\n```
['Depth-First Search', 'C', 'C++']