In the previous video, we have thoroughly understood the question at hand, which is part some two.
And in this video, let's try to think how we can solve this question.
Now in the question, it's mentioned that we have to return all the possible root to leaf paths where
the values of the nodes add up to the target sum.
Now we have seen that because we have to return all the possible root to leaf paths, we can use backtracking
to solve this question.
Now, we have discussed backtracking many times in previous questions.
So that's going to be pretty straightforward.
And it's not going to be difficult.
I'm sure you will be able to do that.
So let's just walk through this and see how it's going to work out.
So we are going to have an array.
So let's just call it cur.
And initially cur will be an empty array.
And when we visit the root node we will fill the value of this node to cur.
So cur at this point will have the value seven.
And then we will just use backtracking to go down each of these branches over here.
Okay.
So when we come over here cur will be seven comma three.
And then we would come over here cur would be seven comma three comma six.
And again we will be checking at this point because we have reached a leaf node.
So we will be checking whether the sum of these elements will equal to the target sum.
But over here we see that the sum is 16 and target sum is 20.
So this is not a solution.
And then because we can't go any further down because this node over here does not have any children,
we will be backtracking.
And to backtrack first we will pop from cur.
Okay.
So this element over here would be removed from cur.
And then we come over here and after that we visit the right path.
So we will be appending the value five when we come over here.
So cur would be seven comma three comma five.
And then we go down further and we reach over here and cur would be seven comma, three comma, five
comma, five.
And because we have reached a leaf node, we will check whether the sum of these values is equal to
target sum.
And we see that it's actually equal to 20.
And therefore we would make a copy of this and append it to the results array.
So let's just call it rest for results okay.
So at this point we would make a copy of this and append it to results.
So this is how we will be solving this question.
It's a typical backtracking approach.
And again an important thing to remember over here is that because nodes can have positive as well as
negative values, you have to keep exploring every branch till you reach the leaf node.
You can't stop in between just because the sum of the values of the elements in Cur is greater than
the target sum.
And again, I am mentioning that over here, because we had previous questions where it was given that
the values in nodes would be positive alone, and because of that, in those questions we could return
whenever we saw that the sum of the values in Cur was greater than target sum.
But that's not the case over here.
So this is how we will be solving this question.