[C++] 3 DFS Based Solutions Explained and Compared, up to ~100% Time, ~75% Space
This is a nice problem, as it is the composition of 2 classical ones: getting a series of values traversing a tree and verifying if any of those numbers have on
This is a nice problem, as it is the composition of 2 classical ones: getting a series of values traversing a tree and verifying if any of those numbers have one or more subarrays summing up to a given `targetSum`.\n\nThe latter problem is [here](https://leetcode.com/problems/subarray-sum-equals-k/) if you want a warm up and [here](https://leetcode.com/problems/subarray-sum-equals-k/discuss/431725/) I explained how it worked in more detail.\n\nSo my approach followed basically these 2 bits of logic, doing a composition of a DFS based tree traversal and at each iteration checking if the very last value mins the `targetSum` were already spotted; I used a vector initially, then moved up to an array to keep track of the already `seen` values with a huge performance boost.\n\nIn my approach I use 3 class variables:\n* my typical accumulator variable `res` initialised to `0` to count the number of matching occurrences;\n* `sum` that takes the values of `targetSum` and replaces it in all of my recursive calls (so that I do not have to pass it as a parameter)\n* `seen`, as mentioned to keep track of the values I spotted so far and created to hold `1001` values (an initial `0` at root level, plus other potential `1000` different ones, as specified in the specs).\n\nInside my main function I initialise the values and then, provided the tree is not empty (ie: `!root`), I call `dfs`.\n\nThis function receives 3 parameters:\n* a mandatory `root`, which is the node we are currently exploring;\n* an optional `partialSum` value, defaulted to `0` and keeping track of our current partial sum going down a specific branch;\n* an optional `pos` to tell us where to put out next value in `seen` and up to which point browse it (muuuch faster than expanding and reducing a vector, try the alternative code down below!)\n\nWe are looking for all the occurrences of values in `seen` which are `partialSum - sum`, because it means that said value `n` plus `partialSum` would equal `sum`, and for each such instance we increase `res` by one.\n\nIf we have a `->left` branch we do the same with it, passing the update `root`, `partialSum` and `pos` (increased by `1`) down as parameters; same thing with a `->right` branch, if it exists.\n\nWhen we are done, we just return `res` :)\n\nThe improved code (using an array for `seen`):\n\n```cpp\nclass Solution {\npublic:\n    int res = 0, sum;\n    int seen[1001];\n    void dfs(TreeNode* root, int partialSum = 0, int pos = 1) {\n        // updating partialSum with the current node\n        partialSum += root->val;\n        // checking if we already found an interval summing up to that\n        for (int i = 0; i < pos; i++) if (seen[i] == partialSum - sum) res++;\n        // updating seen\n        seen[pos] = partialSum;\n        // searching potential left and right branches\n        if (root->left) dfs(root->left, partialSum, pos + 1);\n        if (root->right) dfs(root->right, partialSum, pos + 1);\n    }\n    int pathSum(TreeNode* root, int targetSum) {\n        sum = targetSum;\n        // seen set with initial value 0 will help us match from the root\n        seen[0] = 0;\n        if (!root) return res;\n        dfs(root);\n        return res;\n    }\n};\n```\n\nOriginal approach, vector-based with some extra backtracking logic and going for about a meager ~60% Time, ~50% Space:\n\n```cpp\nclass Solution {\npublic:\n    int res = 0, sum;\n    // seen set with initial value 0 will help us match from the root\n    vector<int> seen = {0};\n    void dfs(TreeNode* root, int partialSum = 0) {\n        // updating partialSum with the current node\n        partialSum += root->val;\n        // checking if we already found an interval summing up to that\n        for (auto n: seen) if (n == partialSum - sum) res++;\n        // updating seen\n        seen.push_back(partialSum);\n        // searching potential left and right branches\n        if (root->left) dfs(root->left, partialSum);\n        if (root->right) dfs(root->right, partialSum);\n        // clearing seen one level, for backtracking purposes\n        seen.pop_back();\n    }\n    int pathSum(TreeNode* root, int targetSum) {\n        sum = targetSum;\n        if (!root) return res;\n        dfs(root);\n        return res;\n    }\n};\n```\n\nAlternative with `unordered_map`, almost as fast, but with space going down to 20% (I believe it used around 40-50% more space on average):\n\n```cpp\nclass Solution {\npublic:\n    int res = 0, sum;\n    unordered_map<int, int> seen;\n    void dfs(TreeNode* root, int partialSum = 0) {\n        // updating partialSum with the current node\n        partialSum += root->val;\n        // checking if we already found an interval summing up to that\n        res += seen[partialSum - sum];\n        // updating seen\n        seen[partialSum]++;\n        // searching potential left and right branches\n        if (root->left) dfs(root->left, partialSum);\n        if (root->right) dfs(root->right, partialSum);\n        // clearing seen of the last value, for backtracking purposes\n        seen[partialSum]--;\n    }\n    int pathSum(TreeNode* root, int targetSum) {\n        sum = targetSum;\n        // seen set with initial value 0 will help us match from the root\n        seen[0] = 1;\n        if (!root) return res;\n        dfs(root);\n        return res;\n    }\n};\n```
['Depth-First Search', 'Recursion', 'C', 'C++']