In this code example, we give two functions that calculate combinations. The first function is recursive and calculates combinations by using the well-known formula c(N, R) = c(N - 1, R) + C(N - 1, R - 1). The second function performs an iterative calculation using the formula C(N, R) = C(N, R - 1)*((N-R+1)/R). In either case, we have C(N, N) = C(N, 0) = 1 and C(N, R) = 0, if R < 0 or R > N. The explicit formula for Combinations is C(N, R) = N!/((N-R)!R!) but is highly susceptible to overflow or rounding errors if used directly.

Combinations tell us the number ways that we can choose R items from N distinct ones. For example, if we have four people. Then there are C(4,2) = 4!/(2!2!) = 6 ways to pick two of the people to work on a project.

Code:

#include <iostream>

int CombinationsRecur(int iN, int iR) {
    if (iR < 0 || iR > iN) {
        return 0;
    }
    if (iR < 1) {
        return 1;
    }
    if (iN == iR) {
        return 1;
    }
    return CombinationsRecur(iN - 1, iR) + CombinationsRecur(iN - 1, iR - 1);
}

int CombinationsIter(int iN, int iR) {
    if (iR < 0 || iR > iN) {
        return 0;
    }
    int iComb = 1;
    int i = 0;
    while (i < iR) {
        ++i;
        iComb *= iN - i + 1;
        iComb /= i;
    }
    return iComb;
}

int main()
{
    for (int i = 0; i < 12; ++i) {
        for (int j = 0; j <= i; ++j) {
            std::cout << CombinationsRecur(i, j) << "  ";
        }
        std::cout << std::endl;
    }

    for (int i = 0; i < 12; ++i) {
        for (int j = 0; j <= i; ++j) {
            std::cout << CombinationsIter(i, j) << "  ";
        }
        std::cout << std::endl;
    }

    return 0;
}

Output: