Hey FreeCodeCamp and welcome to another daily program or web series and in this one
We're going to be talking about the 3-sum problem. Which is number 323 posted on the daily program or subreddit?
Let's go ahead and break it down on the whiteboard
So the 3-sum problem is defined like so, given an array or lists of numbers. print out all the combinations of 3 numbers which when summed up
Equate to zero so for example if I were to try to choose -8 , - 7 and 5 as our first combination
When added together do these sum up to 0 and this will be no because we actually get -10 when we send this up
so then we can try another combination such as -8, 5 and 2 and
When this is sum together we are left with a -1
So again know this combination is not sum to 0 and then the last combination
we can actually try would be - 7 5 and 2
which when summed up it does give us 0
So in this particular input case where we had -8 ,-7 5 and 2,
the only combination of three numbers that sum to 0 would be this combination right here
So we print this out to the console or return in some type of array, and that would be your solution for that input.
So that basically sums up the 3-sum problem
Lets go ahead and break this down further to visualize with more combinations
so let's first reduce the larger problem into something easier to understand such as a sub-problem where how do you find all the
combinations, or you can pick one number and check if it sums as 0
well, obviously we have to loop over all the numbers and only have one variable to keep track of our index and
for each one we just print out the number and check if it equals 0 so i would be 0
and
of course, we increment i
we get -7 we increment i again
to get 5 and
then we increment i one more time to get 2
So that should be obvious right? If you wanted to check all the combinations of one number
You just have the for loop and loop over and print out the number
But now let's say you wanted to print out all the combinations where you would pick two numbers.
So in this case we have to first
keep track of i and then also keep track of j. It should be equal to i + 1
So if you were to increment through this we first print out - 8,
-7
we increment i by 1 or-- sorry, we increment j by 1
to print out -8 and 5
increment j again,
which allows us to print out the combination - 8 and
2, and then when j hits the end of the array we go ahead and increment i by 1 and
set j = i + 1
which gives us -7 in 5 and then increment j again,
which gives us -7 in
2 and
Then lastly we're going to increment i and set j = i + 1 which gives us our last combination
of 5 and 2.
So hopefully that makes sense basically in this case
we have two for loops where we have one loop that loops over i to the end of the array and
then nested inside that we have another loop where j = i + 1 and then we loop to the end of
the array. And that will give us all the different combinations where we can pick two numbers
So then you can kind of intuitively think well if we need to pick 3 numbers for this 3-sum problem
We just need to add another loop, right? So again, let's work through that so instead of just having 2 we'd have an i
we have a j and we have a k.
So starting off, k would be j+1 and j = i +1
So this will give us our first combination of -8 , -7
and 5 and then
we just go ahead and increment
k by 1
Which gives us -8 , -7 and 2 .
Since k is reached the end we increment j by 1 and
then set k = j + 1 which gives us the combination - 8 , - 7 sorry--
-8
5 and 2 and
Then lastly since j has reached the last part of theory that it can get to, we need to increment i by 1
Set j = i +1 and set k = j +1 which will give us a very last combination of - 7
5 and 2 so that's kind of how you work out printing out all the different combinations on paper
And then it should be intuitive how you do that in the computer with 3 4 loops
And then down here you just send them up
See if they equal to 0 and of course the only solution that equals 0 will be this last combination here
So as you add more numbers down the road
Your loops will just go further and further and they print out more combinations
So let's go ahead and go to Javascript and try to implement this logic
So after we're looking at the whiteboard example of how to solve this problem
It should be pretty straightforward of how to implement it right ? We talked about learning in three different loops for i j and k
and the hard part is just going to be figuring out how to initialize our where to initialize the i
j and k add and then how far they should loop over
so starting off is going to write a function called threeSums and it's going to take in a parameter of
numbers
Then in here. We're going to go ahead and declare an array called sets and return that which is going to be
You know all the different combinations?
We found which do match zero and then here we have to start doing our loop so we can say for
Let i = 0 , i < numbers.length - 2
because if you remember, we stopped two away from the ending of the number list
so you can increment that and
Then we can declare a j = i +1
because we need to start 1 after the i and?
Then we can say j < number. length - 1
because again an example. We stopped 1 away from the end because k will always take that last spot
and
Then lastly we can say like k = j + 1
and then k < numbers.length and
then increment k because k will go all the way to the end of the array .
So now that we have our three loops ,what we can do here is declare three numbers
So I'll set const a = numbers[i] , say const b = numbers[j]
and the finally const c = [k]
So that will give us our three numbers to make up the combination
And then lastly we can check if a + b + c = 0
We go ahead and push into that sets array
Those three numbers, so I'll just go ahead and represent that as a string here of a string of a b and C
and
Then at the end. We just return our sets
So now I should be able to run this and should give us all the combinations which sum to zero
So one thing to point out here
Is that what's printed out is going to contain duplicate combinations, and that is because a set that we put in as the input has
Multiple numbers of the same type, so a simple check we can do to make sure that duplicates
do not happen is we can say add an end for this check so a b and C adds together equal zero and
sets index of
Set is equal to -1 then up here. I can say set is equal to that string array
and I can push that
So one more time we're just pulling out that string that picked ,a variable, we're checking if the array already contains
that string or that set
which means index of equal to - 1 which we haven't seen it before and
Then finally we just push it into the set as we did before
So now I run this we hit all the combinations that sum to zero, and we don't get duplicates
All right, so that wraps up the three sums problem
There's other ways to solve this there's actually a faster way to do this
Which if you go to the summer edit you can read about that but for the most part?
I think this is a good overview of how to write code to solve a whole like combinations problem
All right, if you like this tutorial give us a thumbs up and be sure to subscribe to free code camp below alright
Thanks for watching