1
00:00:00,230 --> 00:00:06,320
In the previous video, we have thoroughly understood the question at hand, which is part some two.

2
00:00:06,320 --> 00:00:10,400
And in this video, let's try to think how we can solve this question.

3
00:00:10,400 --> 00:00:18,290
Now in the question, it's mentioned that we have to return all the possible root to leaf paths where

4
00:00:18,290 --> 00:00:21,110
the values of the nodes add up to the target sum.

5
00:00:21,110 --> 00:00:29,120
Now we have seen that because we have to return all the possible root to leaf paths, we can use backtracking

6
00:00:29,150 --> 00:00:30,380
to solve this question.

7
00:00:30,380 --> 00:00:34,490
Now, we have discussed backtracking many times in previous questions.

8
00:00:34,490 --> 00:00:36,710
So that's going to be pretty straightforward.

9
00:00:36,710 --> 00:00:38,150
And it's not going to be difficult.

10
00:00:38,150 --> 00:00:39,800
I'm sure you will be able to do that.

11
00:00:39,800 --> 00:00:43,520
So let's just walk through this and see how it's going to work out.

12
00:00:43,520 --> 00:00:45,770
So we are going to have an array.

13
00:00:45,770 --> 00:00:47,060
So let's just call it cur.

14
00:00:47,060 --> 00:00:49,790
And initially cur will be an empty array.

15
00:00:49,790 --> 00:00:54,860
And when we visit the root node we will fill the value of this node to cur.

16
00:00:54,860 --> 00:00:57,710
So cur at this point will have the value seven.

17
00:00:57,710 --> 00:01:02,900
And then we will just use backtracking to go down each of these branches over here.

18
00:01:02,900 --> 00:01:03,260
Okay.

19
00:01:03,260 --> 00:01:06,920
So when we come over here cur will be seven comma three.

20
00:01:06,920 --> 00:01:12,320
And then we would come over here cur would be seven comma three comma six.

21
00:01:12,320 --> 00:01:16,640
And again we will be checking at this point because we have reached a leaf node.

22
00:01:16,640 --> 00:01:22,190
So we will be checking whether the sum of these elements will equal to the target sum.

23
00:01:22,190 --> 00:01:26,420
But over here we see that the sum is 16 and target sum is 20.

24
00:01:26,420 --> 00:01:28,610
So this is not a solution.

25
00:01:28,610 --> 00:01:34,610
And then because we can't go any further down because this node over here does not have any children,

26
00:01:34,610 --> 00:01:36,260
we will be backtracking.

27
00:01:36,260 --> 00:01:39,650
And to backtrack first we will pop from cur.

28
00:01:39,740 --> 00:01:40,100
Okay.

29
00:01:40,100 --> 00:01:42,800
So this element over here would be removed from cur.

30
00:01:42,800 --> 00:01:47,750
And then we come over here and after that we visit the right path.

31
00:01:47,750 --> 00:01:51,380
So we will be appending the value five when we come over here.

32
00:01:51,380 --> 00:01:54,110
So cur would be seven comma three comma five.

33
00:01:54,110 --> 00:02:00,020
And then we go down further and we reach over here and cur would be seven comma, three comma, five

34
00:02:00,020 --> 00:02:00,980
comma, five.

35
00:02:00,980 --> 00:02:07,610
And because we have reached a leaf node, we will check whether the sum of these values is equal to

36
00:02:07,610 --> 00:02:08,240
target sum.

37
00:02:08,240 --> 00:02:11,180
And we see that it's actually equal to 20.

38
00:02:11,180 --> 00:02:15,410
And therefore we would make a copy of this and append it to the results array.

39
00:02:15,410 --> 00:02:18,350
So let's just call it rest for results okay.

40
00:02:18,350 --> 00:02:22,610
So at this point we would make a copy of this and append it to results.

41
00:02:22,610 --> 00:02:25,400
So this is how we will be solving this question.

42
00:02:25,400 --> 00:02:27,410
It's a typical backtracking approach.

43
00:02:27,410 --> 00:02:33,590
And again an important thing to remember over here is that because nodes can have positive as well as

44
00:02:33,590 --> 00:02:40,160
negative values, you have to keep exploring every branch till you reach the leaf node.

45
00:02:40,160 --> 00:02:46,700
You can't stop in between just because the sum of the values of the elements in Cur is greater than

46
00:02:46,700 --> 00:02:47,420
the target sum.

47
00:02:47,420 --> 00:02:52,580
And again, I am mentioning that over here, because we had previous questions where it was given that

48
00:02:52,580 --> 00:02:58,940
the values in nodes would be positive alone, and because of that, in those questions we could return

49
00:02:58,940 --> 00:03:03,890
whenever we saw that the sum of the values in Cur was greater than target sum.

50
00:03:03,890 --> 00:03:05,510
But that's not the case over here.

51
00:03:05,510 --> 00:03:08,210
So this is how we will be solving this question.