# 12ms 11-lines C++ Solution

• Well, a typical backtracking problem. The code is as follows. You may walk through it using the example in the problem statement to see how it works.

``````class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int> > paths;
vector<int> path;
findPaths(root, sum, path, paths);
return paths;
}
private:
void findPaths(TreeNode* node, int sum, vector<int>& path, vector<vector<int> >& paths) {
if (!node) return;
path.push_back(node -> val);
if (!(node -> left) && !(node -> right) && sum == node -> val)
paths.push_back(path);
findPaths(node -> left, sum - node -> val, path, paths);
findPaths(node -> right, sum - node -> val, path, paths);
path.pop_back();
}
};``````

• This post is deleted!

• I tested your codes, but the running time is not 12ms, but 16ms. I don't know why.

• Hi, YuzeJin. It's Ok. The same piece of code may also have some time variances at different times. The world is just not that accurate :-)

• Is there an iterative solution, jianchao? I have tried, but I find it is difficult to keep track of the path sum.

• Hi, @jin23. I guess for such backtracking-style problems, an iterative solution is somewhat difficult. Yeah, like you mention, it will be difficult to keep track of the necessary information.

• Hi, I have a iterative solution which cost 16ms, the main idea is to use a stack to store the current path, by traversing the tree to find all possible paths to leaf nodes, one's able to get all possible paths that satisfy the sum, maybe you will be interested to take a look:

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
int psum = 0;
vector<TreeNode*> path;
vector<vector<int>> result;

if (!root) return result;

psum += root->val;
path.push_back(root);

TreeNode* cur;
TreeNode* pop = root;

while(!path.empty()) {
cur = path.back();
if (psum == sum && cur->left == NULL && cur->right == NULL) {
vector<int> pathResult;
for(int i = 0; i < path.size(); i++) {
pathResult.push_back(path[i]->val);
}
result.push_back(pathResult);

}

if ((cur->left == NULL && cur->right == NULL) || (cur->right == pop) || (cur->left == pop && cur->right == NULL)) {
pop = cur;
psum -= cur->val;
path.pop_back();
}

else if (cur->left == NULL || cur->left == pop) {
cur = cur->right;
path.push_back(cur);
psum += cur->val;
}

else {
cur = cur->left;
path.push_back(cur);
psum += cur->val;
}

}

return result;
}
};``````

• ``````class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>>  result;
vector<int> solution;
help(root, sum, result, solution);
return result;
}

void help(TreeNode* root, int sum, vector<vector<int>> &result, vector<int> solution){
if(!root)   return;
//leat node
if(!root->left && !root->right && root->val==sum) {
solution.push_back(root->val);
result.push_back(solution);
return;
}
//not leaf node
solution.push_back(root->val);
if(root->left)  {
help(root->left, sum-root->val, result, solution);
}
if(root->right)  {
help(root->right, sum-root->val, result, solution);
}
}
};``````

• Just want to point out, your program's space cost is too high as you need to maintain a vector<int> for each function call. I believe you can improve that by using a reference.

• If you do not use pass by reference for "paths" ( i.e., "vector<vector<int> >& paths" to "vector<vector<int> > paths" ), You don't need "path.pop_back();" anymore.

• I love this passing by reference and pop_back idea

• My code is almost the same as yours but costs 24 ms... IDK why.

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
vector<int> currVct;
helper(root, sum, res, currVct);
return res;
}

void helper(TreeNode* root, int sum, vector<vector<int>>& res, vector<int> currVct) {
if (!root) {
return ;
}
sum -= root -> val;
currVct.push_back(root -> val);
if (!root -> left && !root -> right) {
if (sum == 0) {
res.push_back(currVct);
}
return ;
}
helper(root -> left, sum, res, currVct);
helper(root -> right, sum, res, currVct);
}
};``````

• @lijunray
By the end of each recursive search, you need to pop_back() (delete the number) if the search fails. If you don't have this step, the code will return a traversal of the whole branch (because you have tried all possible leaves in the tree).

• @justin40 Thank you!

• This works without the last line of pop_back(). I think its not required

I comment-out the line. The result includes all the fail paths as I expected. Can you post your accepted code? Maybe we are using different method.

• @justin40
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
vector<int> temp;
hasPathSum(root,sum,res,temp);
return res;
}
void hasPathSum(TreeNode* root, int sum,vector<vector<int>> &res,vector<int> temp) {

``````    if(root==NULL)
return;
temp.push_back(root->val);
if(root->val==sum && root->left==NULL && root->right==NULL)
{
res.push_back(temp);
}
hasPathSum(root->left,sum-root->val,res,temp);
hasPathSum(root->right,sum-root->val,res,temp);

}
``````

};