# Count Total Possible Path with Given Sum

You are given a matrix of size *N*M* with each cell having some values, you need to find the number of paths from first cell to last bottom right cell such that the path has exactly given sum. You can only move in two direction either right or down.

**Problem description:**

The problem wants you to use the logic that if you are at position *(i,j)* then you can only move in the right and down direction that is *(i+1,j)* or *(i,j+1)* and if we move from bottom right to top left then *(N-1, M-1)* to *(0,0)* then it is left or up movement along with that you need to keep in mind that the sum that you used during the traversal should be equal to the given sum. Finally, you need to print the total count of that path which follows given constraints.

**Input:**

The first line of input is *T* number of test cases, each test case consist of two integers *N* and *M* the size of matrix. Each of the following

**Output:**

You need to print the count of total number of paths that are possible with given sum.

**Examples:**

Input:
T=1
N=3,M=3
1 2 3
4 5 6
7 8 9
sum=21
Output:
1,
as 1->2->3->6->9 is the only path possible which
has sum equal to 21.

(a) Recursion Approach:In this method we will use recursion to solve the given problem, we will move from the bottom right to top left since we can move only right or down if we start from top left and move to the bottom right, and up and left if the move from bottom right to top left. We will start from the cell(n-1,m-1) and move to (0,0) each time we will decrease the sum and finally, we will check if is it possible to reach the cell(0,0), if the sum remaining with us is equal to the cost present at cell(0,0) then we return 1 as one path is possible.

We will follow the recursive function:

Time complexityfor the above case in the worst case is.exponentialSpace complexityfor the above case in the worst case is:.O(1)(b) Dynamic Programming Approach:In this method we will use memorization, we will create a

dp[][][]state, we need to create a 3-D dp state because the given function depends directly on three different quantities n,m, and cost. Each time we make a function call we will store the result the value of that function call on adp[][][]state and if we make again the same call then we would check it in the dp table if already calculated then we will directly return without calculating it again and again.The base cases for this dp approach is the same as the recursion approach as:

sumis less than 0 then we return 0.sumremaining then we return 1 otherwise return 0.Time complexityfor the above approach in the worst case is:O(N*M*sum)Space complexityfor the above approach in the worst case is:O(N*M*sum)C++ Implementation (Recursion Approach):Output:C++ Implementation (Dynamic Programming Approach):

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: