CareerCup

Let a = x2 - x1 and b = y2 - y1

The answer is then C(a+b, b) (or C(a+b, a) -- these are equal) where C is the binomial coefficient function (sometimes read as "a+b choose a"). The reason is that you need to take a+b steps to reach your goal, and any b of those can be upward steps (or alternatively, any a of those can be to the right). The answer is therefore the number of different ways to pick b items from a sequence of length a+b.

Using a formula for the binomial coefficient, C(a+b, a) = (a+b)! / (a! * b!)

int countPaths(int x1, int y1, int x2, int y2) {
int count=0;
if ((x1>x2) || (y1>y2)) {
return 0;
}
if ( x1==x2 && y1==y2 ) {
return 1;
}
count = countPaths(x1+1,y1,x2,y2) + countPaths(x1,y1+1,x2,y2);
return count;
}