Interesting thing that I knew about combinations - is that you can precompute them using pascal triangle.

Generally the formula is:
C(n, k) = n! / (k! · (n − k)!)

Pascal triangle formula is:
C(n, k) = C(n−1, k−1) + C(n−1, k)

===

It is nice, cause I always keep forgetting combinations formula, and it is very hard for me to recreate it from the simple examples.

Now on the interview I can just state: there is formula, I don't remember but I know Pascal triangle will do the job.

#leetcode #datastructures #math