n개중에서 r개를 뽑는 경우는 nCr이라는 공식을 이용하여 풀수 있다.
nCr = n! / r! x (n-r)! 이다
하지만 이것을 컴퓨터에게 그대로 적용시켜 계산하게 되면 오버 플로우가 일어날 수 있다.
n!의 경우 n값이 조금만 크더라도 n!값이 엄청 커진다.
이를 방지 하기 위해서 점화식을 이용해서 풀면 된다.
nCr = (n - r + 1) / r * nCr-1
nC0 = 1( r = 0일때)
이런식으로 점화식을 이용해서 풀면 오버 플로우를 막을 수 있다.
double combination( int n, int r )
{
int i;
double sum;
sum = 1;
for( int i =1; i <= r; i++ )
sum = sum * (( n - i + 1 ) / (double) i );
return sum;
}