Recursive nCr Combinations in Java

Question

I have an assignment to create two recursive methods (in Java) which calculate nCr. The first method I wrote was one using Pascal's triangle. It works, Pascal triangle's is fabulous.

But now I'm in a problem as I can't think/find any other recursive solutions two write my second method which calculates nCr. I have tried using/writing a method based on finding out the factorial but that one cracks when I use big numbers.

Can someone, please, give me some tips, suggestions, advises regarding other recursive ways of calculating nCr?

Many thanks!

Answer 1

I can offer the solution of your problem, created in C++.

#include <iostream>
#include <cstring>
int dp[100][100];
int choose(int a, int b)
{
    if(a < b) return 0;
    if(dp[a][b] != -1) return dp[a][b];
    if(b == 0) return 1;
    if(b == 1) return a;
    dp[a][b] = (choose(a - 1, b) + choose(a - 1, b - 1));
    return dp[a][b];
}
int main()
{
    memset(dp, -1, sizeof(dp));
    return 0;
}