The best programs are written so that computing machines can perform
them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist
who works with traditional aesthetic and literary forms as well as mathematical concepts, to
communicate the way that an algorithm works and to convince a reader that the results will be correct.
― Donald E. Knuth

Problem :-
Evaluate ^{n}C_{r} i.e combination ( n, r ). Combination refer to the combination of n things taken r at a time without repetition.
Mathematically, ^{n}C_{r} = n! / r! * ( n - r )!

Solution :-
Let C ( n , r ) denotes combination of n things taken r at a time.
As per recursive formulation, C ( n , r ) = C ( n - 1 , r - 1 ) + C ( n - 1 , r ) with
C ( n , 0 ) = C ( n , n ) = 1. This is basically the structure of an optimal solution defined recursively.
We can maintain a 2D array C [ n + 1 ][ r + 1 ] which stores all the combination values starting from C ( 0 , 0 ).
Finally, C [ n ][ r ] gives the value of C ( n , r ).
See the program below for the solution.

#include<iostream>using namespace std;
// find C(n,r)
// Standard recursive formula for computing C(n,r)
// C(n,r) = C(n-1,r-1) + C(n-1,r)
// where C(n,0) = C(n,n) = 1int choose(int n,int r) {
if(r == 0 || r == n)
return 1;
// store C(n,r) in a matrix int c[n+1][r+1];
int i,j;
for(i=0;i<=n;i++) {
// C(i,0) = 1 for i = 0...n
c[i][0] = 1;
}
for(j=0;j<=r;j++) {
// if n = 0, C(n,r) = 0 for all 'r'
c[0][j] = 0;
}
for(i=1;i<=n;i++) {
for(j=1;j<=r;j++) {
if (i == j) {
// C(n,n) = 1
c[i][j] = 1;
}
else if (j > i) {
// case when r > n in C(n,r)
c[i][j] = 0;
}
else {
// apply the standard recursive formula
c[i][j] = c[i-1][j-1] + c[i-1][j];
}
}
}
return c[n][r];
}
// mainint main() {
int n = 5,r = 2;
int comb = choose(n,r);
cout<<"C("<<n<<","<<r<<") :: "<<comb;
cout<<endl;
return 0;
}

#include<iostream>using namespace std;
// find C(n,r)
// Standard recursive formula for computing C(n,r)
// C(n,r) = C(n-1,r-1) + C(n-1,r)
// where C(n,0) = C(n,n) = 1int choose(int n,int r) {
if(r == 0 || r == n)
return 1;
// store C(n,r) in a matrix int c[n+1][r+1];
int i,j;
for(i=0;i<=n;i++) {
// C(i,0) = 1 for i = 0...n
c[i][0] = 1;
}
for(j=0;j<=r;j++) {
// if n = 0, C(n,r) = 0 for all 'r'
c[0][j] = 0;
}
for(i=1;i<=n;i++) {
for(j=1;j<=r;j++) {
if (i == j) {
// C(n,n) = 1
c[i][j] = 1;
}
else if (j > i) {
// case when r > n in C(n,r)
c[i][j] = 0;
}
else {
// apply the standard recursive formula
c[i][j] = c[i-1][j-1] + c[i-1][j];
}
}
}
return c[n][r];
}
// mainint main() {
int n = 5,r = 2;
int comb = choose(n,r);
cout<<"C("<<n<<","<<r<<") :: "<<comb;
cout<<endl;
return 0;
}