Approach 1:
C(n,r) = n!/(n-r)!r!

Approach 2:

I discovered this in Wilf's book Combinatorial Algorithms: C(n,r) may be represented as C(n-1,r) + C (n-1,r-1).

e.g.

```C(7,4) = C(6,4) + C(6,3)
= C(5,4) + C(5,3) + C(5,3) + C(5,2)
.   .
.   .
.   .
.   .
After solving
= C(4,4) + C(4,1) + 3*C(3,3) + 3*C(3,1) + 6*C(2,1) + 6*C(2,2)```

As you can see, there is no need for multiplication in the final result.

In every C(n,r) form, either n==r or r==1.

Here is an example of the code I used:

```int foo(int n,int r)
{
if(n==r) return 1;
if(r==1) return n;
return foo(n-1,r) + foo(n-1,r-1);
}```

Approach 2 has overlapping sub-problems where we use recursion to tackle the same sub-problems again.

Using Dynamic Programming, we can prevent this.

Which method is preferable for calculating C(n,r)?

Jul 25, 2022 in C++ 329 views

## What is the best way to use a HashMap in C++?

The ordered and unordered map containers (std::map and std::unordered map) are included in the standard library.  The items in an ordered map are sorted by key, and insert and access are in O (log n).  For ordered maps, the standard library often use red black trees.  However, this is only an implementation detail.  Insert and access are in O in an unordered map (1).  It is simply another term for a hashtable. An illustration using (ordered) std::map: #include <map> #include <iostream> #include <cassert> int main(int argc, char ...READ MORE

## What is the easiest way to initialize a std::vector with hardcoded elements?

I can make an array and initialise&nb ...READ MORE

## Is there an easy way to make a min heap in C++?

Use make heap() and its buddies from algorithm>, or priority queue from queue>.  Make heap and friends are used by priority queue. #include <queue> // functional,iostream,ctime,cstdlib using namespace std; int main(int ...READ MORE

## What is the fastest way to transpose a matrix in C++?

I have a reasonably large matrix that I need to transpose.  Assume, for example, that my matrix is a b c d e f g h ...READ MORE

## Visual C++ vs Visual C# , which is the best to learn?

I completed my C++ lessons and practises ...READ MORE

## What is the difference between cout, cerr, clog of iostream header in c++? When to use which one?

I looked up the differences between cout, ...READ MORE

## Why would anyone use set instead of unordered_set?

Unordered sets must compensate for their O(1) ...READ MORE

## Ternary operator ?: vs if...else

It's not any faster.  There is one difference when you can initialize a constant variable using an expression: const int x = (a<b) ? b ...READ MORE