1
00:00:00,230 --> 00:00:01,340
Welcome back.

2
00:00:01,340 --> 00:00:04,820
Previously we have solved combination sum one.

3
00:00:04,820 --> 00:00:10,520
Now over here, let's get started with another interesting question which is combination sum two.

4
00:00:10,550 --> 00:00:17,390
So the question reads given a collection of candidate numbers candidates and a target number target,

5
00:00:17,390 --> 00:00:25,400
find all unique combinations in candidates where the candidate numbers sum to target.

6
00:00:25,700 --> 00:00:30,920
Each number in candidates may only be used once in the combination.

7
00:00:30,920 --> 00:00:36,020
Note the solution set must not contain duplicate combinations.

8
00:00:36,020 --> 00:00:38,300
So over here we are given an example as well.

9
00:00:38,300 --> 00:00:45,170
So let's say the input is 35213 and the target number which is given to us is seven.

10
00:00:45,170 --> 00:00:47,990
Then the output is an array of arrays.

11
00:00:47,990 --> 00:00:55,220
And over here each element in this array over here has elements inside it with sum up to the target

12
00:00:55,220 --> 00:00:55,610
value.

13
00:00:55,610 --> 00:00:59,630
So one plus three plus three seven and five plus two is seven.

14
00:00:59,630 --> 00:01:05,690
Now again notice in this question it says that each number may only be used once.

15
00:01:05,690 --> 00:01:08,090
So for example over here you have five and two.

16
00:01:08,090 --> 00:01:10,970
And over here you have one three and three.

17
00:01:10,970 --> 00:01:15,860
But this is not a violation because you are given two threes in the input array.

18
00:01:15,860 --> 00:01:20,150
And we're just using every element in the input array one time.

19
00:01:20,150 --> 00:01:21,530
So this is the question.

20
00:01:21,530 --> 00:01:29,780
Now notice also that it's mentioned over here that the output array must not contain duplicates.

21
00:01:30,050 --> 00:01:31,580
So what would that mean.

22
00:01:31,580 --> 00:01:39,710
Let's say for the sake of our discussion, if the target value was four instead of seven, then if one

23
00:01:39,710 --> 00:01:42,350
element in the output array is three comma one.

24
00:01:42,350 --> 00:01:49,880
Taking this three and this one and another element is one comma three taking this one and this three,

25
00:01:49,880 --> 00:01:52,670
then these two would be duplicates.

26
00:01:52,670 --> 00:01:59,540
And it's mentioned in the question that the solution set must not contain duplicate combinations.

27
00:01:59,540 --> 00:02:00,860
So this is the question.

28
00:02:00,860 --> 00:02:04,970
Now in the next video let's try to think about how we can solve this.

29
00:02:04,970 --> 00:02:11,030
And let's also compare this with combination sum one so that we can understand the differences between

30
00:02:11,030 --> 00:02:17,630
these two questions and how the approach has to be slightly tweaked to solve this question.