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.
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.
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
You need to print the count of total number of paths that are possible with given sum.
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 complexity for the above case in the worst case is exponential.
Space complexity for 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 a dp 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:
Time complexity for the above approach in the worst case is: O(N*M*sum)
Space complexity for the above approach in the worst case is: O(N*M*sum)
C++ Implementation (Recursion Approach):
C++ Implementation (Dynamic Programming Approach):
Output:need an explanation for this answer? contact us directly to get an explanation for this answer