How to solve the combinatoric selections problem

Combinatoric selections is problem #53 on Project Euler. The problem statement is as follows.

There are exactly ten ways of selecting a combination of three from five numbers, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation ${5 \choose 3} = 10$.

In general, ${n \choose r} = \frac{n!}{r!(n-r)!}$, where $r \le n$. $n! = n \times (n-1) \times ... \times 3 \times 2 \times 1$, and $0! = 1$.

It is not until $n=23$ that a value exceeds one million: ${23 \choose 10} = 1144066$.

How many not necessarily distinct values of ${n \choose r}$ for $1 \le n \le 100$ are greater than one million?

C++ solution

Explanation

The problem is quite simple. All we are required to do is calculate ${n \choose r}$ for $2 \le n \le N$ and return the count of the number of values above a certain threshold, $K$.

The naive approach is to calculate the value of ${n \choose r}$ using the formula provided in the problem statement. However, that approach, while correct, is slow and inefficient. Moreover, it suffers from integer overflows when calculating the factorials and can give inaccurate results.

A much better approach is to generate Pascal’s triangle. This method is faster because it only uses the addition operation instead of having to calculate large factorials and then perform multiplication and division operations on them.

We generate Pascal’s triangle in the main for loop. There are three conditions for which we fill a slot with $1$:

• If the row index is 0, meaning we are at the topmost block.

• If the column index is 0, meaning we are at the beginning of a row.

• If the column and row index are equal, meaning we are at the end of a row.

We deal with these three conditions in the following code snippet:

if(i == 0 || j == i || j == 0){
    pascalsTriangle[i].push_back(1);
}

For the rest of the slots, we use the slots above them and add them together to get the value of the new block. The slots that we use are the ones directly above the new block, at position [row - 1][columns] and the one adjacent to it at position [row - 1][columns - 1].

The most important part is in the last if condition. We check if the new number is greater than or equal to $K$, and if so, we increment the count. An important step is to set the number to $K$ as well. This will prevent integer overflow errors for large values of $N$.