Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.
How many routes are there through a 20×20 grid?
I recognized this as a Binomial Coefficient problem of given n things, how many ways could you choose m things? I looked briefly but didn’t find any Java classes that implemented this, so I implemented it myself.
String answer = ""; BigInteger value = nChooseM(40,20); answer = value.toString(); System.out.println("Answer: "+answer);
Note: “nChooseM” is a Mathematical Combination function I implemented using BigInteger. 40 choose 20 because there are 40 moves (20 left, 20 down), in the 20×20 grid. In the example, it would be 4 choose 2 = 6.