(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:

f(n,m,sum)= f(n,m-1,sum-mat[n][m]),if n==0.
    = f(n-1,m,sum-mat[n][m]),if m==0.
    = f(n-1,m,sum-mat[n][m])+f(n,m-1,sum-mat[n][m]),in all other cases.

f(0,0,sum)= 1,if(sum==mat[n][m])
    = 0,in other cases.

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:

• If the sum is less than 0 then we return 0.
• If we reached the top-left corner and the value at that cell is equal to the sum remaining then we return 1 otherwise return 0.
• If we have already calculated the given function value then we simply return from the dp table.
• Otherwise, we recursively move in the left and upward direction and finally store their value in the dp table.

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):

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//matrix to store values for
//different cell.
ll mat[1003][1003];

//solve function which will return
//total number of possible path.
ll solve(ll n, ll m, ll sum)
{
    //base case if sum <0 then
    //no path is possible.
    if (sum < 0)
        return 0;

    //if first cell is reached.
    if (n == 0 and m == 0) {
        //check if value at first cell
        //is same as remaining sum.
        if (mat[n][m] == sum)
            return 1;
        else
            return 0;
    }

    //if first row then we can move
    //only in left direction.
    if (n == 0)
        return solve(n, m - 1, sum - mat[n][m]);

    //if first column then we can
    //only move in upward direction.
    if (m == 0)
        return solve(n - 1, m, sum - mat[n][m]);

    //other cases.
    return solve(n - 1, m, sum - mat[n][m]) + solve(n, m - 1, sum - mat[n][m]);
}

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of matrix: ";
        ll n, m;
        cin >> n >> m;
        
        cout << "Enter elements:\n";
        for (ll i = 0; i < n; i++) {
            for (ll j = 0; j < m; j++)
                cin >> mat[i][j];
        }
        
        ll sum;
        
        cin >> sum;
        
        cout << "Total possible path: ";
        cout << solve(n - 1, m - 1, sum) << "\n";
    }
    
    return 0;
}

Output:

Enter number of test cases: 2
Enter size of matrix: 2 2
Enter elements:
1 2 
3 4
8
Total possible path: 1
Enter size of matrix: 2 2
Enter elements:
1 2
3 4
5
Total possible path: 0

C++ Implementation (Dynamic Programming Approach):

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//matrix to store values for
//different cell.
ll mat[1003][1003];

//initialize dp state.
ll dp[101][101][101];

//solve function which will return
//total number of possible path.
ll solve(ll n, ll m, ll sum)
{
    //base case if sum <0 then
    //no path is possible.
    if (sum < 0)
        return 0;

    //if first cell is reached.
    if (n == 0 and m == 0) {
        //check if value at first cell
        //is same as remaining sum.
        if (mat[n][m] == sum)
            return 1;
        else
            return 0;
    }
    //check is given function value
    //already calculated then return directly.
    if (dp[n][m][sum] != -1)
        return dp[n][m][sum];

    //if first row then we can move
    //only in left direction.
    if (n == 0)
        return dp[n][m][sum] = solve(n, m - 1, sum - mat[n][m]);

    //if first column then we can
    //only move in upward direction.
    if (m == 0)
        return dp[n][m][sum] = solve(n - 1, m, sum - mat[n][m]);

    //other cases.
    return dp[n][m][sum] = solve(n - 1, m, sum - mat[n][m]) + solve(n, m - 1, sum - mat[n][m]);
}

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of matrix: ";
        ll n, m;
        cin >> n >> m;

        cout << "Enter elements:\n";
        for (ll i = 0; i < n; i++) {
            for (ll j = 0; j < m; j++)
                cin >> mat[i][j];
        }

        memset(dp, -1, sizeof(dp));

        ll sum;

        cin >> sum;

        cout << "Total possible path: ";
        cout << solve(n - 1, m - 1, sum) << "\n";
    }

    return 0;
}

Output:

Enter number of test cases: 2
Enter size of matrix: 4 4
Enter elements:
4 7 1 6
5 7 3 9
3 2 1 2
7 1 6 3
25
Total possible path: 2
Enter size of matrix: 3 3
Enter elements:
1 2 3
4 5 6
7 8 9
21
Total possible path: 1