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.
1 2 3
4 5 6
7 8 9
as 1->2->3->6->9 is the only path possible which
has sum equal to 21.