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:
ABCFI, ABEHI, ADGHI, ADEFI, ADEHI, ABEFI.

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 .

now Lets jump to Solution 

My Approach -

let's think about base condition 

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 -