CareerCup

If the paths can only go down or right then straightforward dynamic programming can be used to solve the problem. To reach (y,x) you have to either reach (y-1,x) or (y,x-1) immediately prior; so the number of paths for these two sub-problems are added together.

P(y, x) = P(y-1, x) + P(y, x-1)
    P(0, x) = 1
    P(y, 0) = 1

This can be done either bottom up (with a table), or top down (with memoization and recursion).

C(M + N, N) or C(M + N, M)

#include<stdio.h>
int count = 0;
void Recursion(int right, int down) {
if (right == 1 && down == 1) {
count++;
return;
}
if (down > 1){Recursion(right, down-1);}
if (right > 1){Recursion(right-1, down);}
return;
}
int main() {
int i = 0, m, n;
printf("Enter value of m & n: ");
scanf("%d %d", &m, &n);
Recursion(m, n);
printf("Count: %d", count);
return 0;
}