<p>Given the <code>root</code> of a binary tree and an integer <code>targetSum</code>, return <em>the number of paths where the sum of the values&nbsp;along the path equals</em>&nbsp;<code>targetSum</code>.</p>

<p>The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/09/pathsum3-1-tree.jpg" style="width: 450px; height: 386px;" />
<pre>
<strong>Input:</strong> root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
<strong>Output:</strong> 3
<strong>Explanation:</strong> The paths that sum to 8 are shown.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
<strong>Output:</strong> 3
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is in the range <code>[0, 1000]</code>.</li>
	<li><code>-10<sup>9</sup> &lt;= Node.val &lt;= 10<sup>9</sup></code></li>
	<li><code>-1000 &lt;= targetSum &lt;= 1000</code></li>
</ul>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        int num_paths = 0;
        std::vector<std::vector<int>> all_paths;
        dfs(root, {}, targetSum, all_paths, num_paths); 
        // PathSumEqualsTarget(all_paths, targetSum, num_paths);
        return num_paths;
    }

    void dfs(TreeNode* root, std::vector<int> path, const int& targetSum, std::vector<std::vector<int>>& all_paths, int& num_paths){
        if (!root) { return;}

        path.push_back(root->val);

        if (is_leaf(root)){
            all_paths.push_back(path);
        }

        PathSumEqualsTarget(path, targetSum, num_paths);


        dfs(root->left, path, targetSum, all_paths, num_paths);
        dfs(root->right, path, targetSum, all_paths, num_paths);

    }

    void PathSumEqualsTarget(const std::vector<int>& path, const int& targetSum, int& num_paths){

        for (int i = 0; i < path.size(); ++i){
            long int current_sum = 0;
            for (int j = i; j< path.size(); ++j){
                current_sum += path[j];
                // if (std::abs(current_sum)>std::abs(targetSum)){
                //     break;
                // } 
            }

              if (current_sum==targetSum){
                    num_paths += 1;
                    // break;
                }
        }
    }

    bool is_leaf(TreeNode* root){
        return ((!root->left) && (!root->right));
    }


//  void PathSumEqualsTarget(const std::vector<std::vector<int>>& all_paths, const int& targetSum, int& num_paths){

//     for (const auto &path:  all_paths){
//         for (int i = 0; i < path.size(); ++i){
//             std::cout << path[i] << std::endl;
//             int current_sum = 0;
//             for (int j = i; j< path.size(); ++j){
//                 current_sum += path[j];
//                 if (current_sum==targetSum){
//                     // std::cout << "current_sum " << current_sum << " pj " << path[j] << " -1 " <<  path[j-1] << std::endl;
//                     num_paths += 1;
//                     break;
//                 } 
//             }

//         }
//      }
//     }
   

};

                    // std::cout << "current_sum " << current_sum << " pj " << path[j] << " -1 " <<  path[j-1] << std::endl;
                    // num_paths += 1;
                    // break;
75374