# Number of paths Recursion Basic Problem-

### Problem Statement-

The problem is to count all the possible paths from top left to bottom right of a MxN matrix with the constraints that from each cell you can either move to right or down.

Input:
The first line of input contains an integer T, denoting the number of test cases. The first line of each test case is M and N, M is number of rows and N is number of columns.

Output:
For each test case, print the number of paths.

Constraints:
1 ≤ T ≤ 30
1 ≤ M,N ≤ 10

Example:
Input
2
3 3
2 8

Output
6
8

Explanation:
Testcase 1:
Let the given input 3*3 matrix is filled as such:
A B C
D E F
G H I

The possible paths which exists to reach 'I' from 'A' following above conditions are as follows:

This is Strongly recommended that You should try This question to your own before jumping to direct solution

Try this question Yourself Practice here-gfg Rat in A mace

Now My Solution-

We can solve this question  recusively

There can be 2 type of problems here one we have to print path(needed 2d array) and one we have to tell number of total path.

In this question I will focus only number of total path If you want print the Number of paths also

i will write solution for that too comment below this post for that printing path .

My Approach -

if we have only one element then we have only one path (return 1) and if we go out of m,n then we don't have any solution so we will return 0 in that case.

if(i>=m||j>=n){

return 0;

}

if(i==m-1&&j==n-1){

return 1;

}

See recustion is  a topic where you have to think about sub problem what i am thinking now  if i am standing at a generic position lets say at index i,j  i have 2 choices form my poison either i can go to right j+1th poison where j  denoting column index or i can go down at i+1th row.

So here i got my induction step -

return solution(i+1,j,m,n)+solution(i,j+1,m,n);

according to these concept i can write my code . Here is my solution -