Combination Formula

It is a formula used to determine the number of ways to select items from a larger set where the order does not matter. It is expressed as:

C(n, r) = n! / r!(n - r)!

N is the total number of items, and r is the number of items to choose. (if N is for example 5, then r has to be between 0 and 5).

Simple O(n) function:

int C(int n, int r) {
  int t1, t2, t3;
  t1 = fact(n);
  t2 = fact(r);
  t3 = fact(n - r);
  return t1 / t2 * t3;
}

We can for example use this formula for Pascal's triangle. Such triangle can also be used to determine how the recursive version of this function might look like.

Using recursion:

int C(int n, int r) {
  if (r == 0 || n == r)
    return 1;
  else
    return C(n - 1, r - 1) + C(n - 1, r);
}

Coding time:

#include <stdio.h>

int fact(int n) {
  if (n == 0)
    return 1;
  return fact(n - 1) * n;
}

int nCr(int n, int r) {
  int num, den;

  num = fact(n);
  den = fact(r) * fact(n - r);

  return num / den;
}

int NCR(int n, int r) {
  if (n == r || r == 0) {
    return 1;
  }
  return NCR(n - 1, r - 1) + NCR(n - 1, r);
}

int main() {
  printf("%d \n", NCR(5, 2));
  return 0;
}