Java Combinatorics using Memoization/Dynamic Programming

Going by the formula for n choose k = ( n - 1 choose k - 1) + ( n-1 choose k ) the bottom up dynamic programming approach would be:

dp[n][k] = dp[n-1][k-1] + dp[n-1][k] if n > k 
else if n == k
dp[n][k] = 1
else
dp[n][k] = 0

start from n = 1 and k = 1

dp[1][1] = 1; dp[1][0] = 1; 

and then fill a two dimensional array till dp[n][k]

It could also be done with memoization as in your case. Your method could be changed to :

int[][] dp = new int[group][members];

public static int combinations(int group, int members, int[][] dp ) {

    if (members == 1) {
        return group;
    } else if (members == group) {
        return 1;
    }

    if ( dp[group][members] != 0 ) {
       return dp[group][members];
    }

    int first = 0, second = 0;
    if ( members <= group - 1) {
      first = combinations( group - 1, members - 1, dp );
      second = combinations( group - 1, members );
    } else if ( members - 1 <= group - 1 ) {
      first = combinations( group - 1, members - 1, dp );
    }
    dp[group][members] = first + second;

    return dp[group][members];
}

One way is to do caching, which comes with the great price of memory usage.

public static int combinations(int group, int members) {
    if (members > group - members) {
        members = group - members; // 21 choose 17 is same as 21 choose 4
    }

    final int[][] cache = new int[group][members];
    return combinations(group, members, cache);
}
private static int combinations(int group, int members, int[][] cache) {
    if (cache[group - 1][members - 1] > 0) {
        return cache[group - 1][members - 1];
    }
    else if (members == 1) {
        cache[group - 1][members - 1] = group;
        return group;
    }
    else if (members == group) {
        cache[group - 1][members - 1] = 1;
        return 1;
    }
    else {
        return (combinations(group - 1, members - 1, cache) + combinations(group - 1, members, cache));
    }
}

I did some quick test (non-professional benchmarks) and found that the original method takes half the time of the caching method. Looks like all these read/writes to the array cache is slowing things down drastically.

The other way is to change the whole formula.

public static int combinations(int group, int members) {
    if (members > group - members) {
        members = group - members;
    }

    int answer = 1;
    for (int i = group; i > group - members; i--) {
        answer *= i;
    }

    for (int i = 1; i <= members; i++) {
        answer /= i;
    }

    return answer;
}

Again, I tested the new method with the original (which I made them use BigInteger for the test), and the new method is incredibly faster (26 seconds for original method vs 0.00 seconds for the latter for 35 choose 15).

To add on a bit, I think the time complexity for using recursive call is O((group)(log members)), while using the new formula is simply O(members).