In this video, let's step aside for a moment to quickly discuss what NCR is.
So NCR is a notation that indicates the number of ways in which you can choose our things from n things.
For example, if n is five and r is two, you would get five, c two and five.
C two represents the number of ways in which you can choose two items out of five items.
For example, let's say you have five people over here.
And if you want to create a group of two people, then to identify the number of ways in which you can
do this, you can just do 5C2.
Now there is a formula for this.
We'll come to that in a minute.
But to first build a solid understanding of what NCR is let's take an example.
So over here I have a b c d e.
Now let's say I want to choose two letters out of these five letters.
Now the different ways in which I can do that is I could have a and B, a and C, a and d or a and e
b and c, b and d b and e c, d, c and d.
So over here I have four ways.
We have three ways then two and one.
So the total number of ways in which I can choose two items out of five items is equal to ten.
So there are ten ways of doing it now because writing out things in this manner is difficult and not
always practical.
There is a formula that we can use to calculate 5C2.
So NCR is actually equal to n factorial by r factorial into n minus r factorial.
So 5C2 would be five factorial divided by two factorial.
Because r is equal to two and then you have n minus r factorial which is five minus two factorial.
Now five factorial is just five into four into three into two into one.
And then you have two factorial and you have three factorial over here.
So five into four into three into two into one.
And then two factorial is just two into one which is two and three factorial is three into two.
Now on simplifying notice that this becomes five into two which is equal to ten.
And that's what we got over here so quickly.
Recapping NCR represents the number of ways in which we can choose our things out of n things.
And to find NCR you can just do n factorial divided by r factorial into n minus r factorial.
Now, the reason why I have discussed this over here is because this concept is helpful when we discuss
the time complexity of the approach that we have discussed so far for solving the palindrome partitioning
question.
Let's see more of that in the next video.