Number of combinations (N choose R) in C++

Question

Here I try to write a program in C++ to find NCR. But I've got a problem in the result. It is not correct. Can you help me find what the mistake is in the program?

#include <iostream>
using namespace std;
int fact(int n){
    if(n==0) return 1;
    if (n>0) return n*fact(n-1);
};

int NCR(int n,int r){
    if(n==r) return 1;
    if (r==0&&n!=0) return 1;
    else return (n*fact(n-1))/fact(n-1)*fact(n-r);
};

int main(){
    int n;  //cout<<"Enter A Digit for n";
    cin>>n;
    int r;
         //cout<<"Enter A Digit for r";
    cin>>r;
    int result=NCR(n,r);
    cout<<result;
    return 0;
}

Answer 1

The definition of N choose R is to compute the two products and divide one with the other,

(N * N-1 * N-2 * ... * N-R+1) / (1 * 2 * 3 * ... * R)

However, the multiplications may become too large really quick and overflow existing data type. The implementation trick is to reorder the multiplication and divisions as,

(N)/1 * (N-1)/2 * (N-2)/3 * ... * (N-R+1)/R

It's guaranteed that at each step the results is divisible (for n continuous numbers, one of them must be divisible by n, so is the product of these numbers).

For example, for N choose 3, at least one of the N, N-1, N-2 will be a multiple of 3, and for N choose 4, at least one of N, N-1, N-2, N-3 will be a multiple of 4.

C++ code given below.

int NCR(int n, int r)
{
    if (r == 0) return 1;

    /*
     Extra computation saving for large R,
     using property:
     N choose R = N choose (N-R)
    */
    if (r > n / 2) return NCR(n, n - r); 

    long res = 1; 

    for (int k = 1; k <= r; ++k)
    {
        res *= n - k + 1;
        res /= k;
    }

    return res;
}