Home » Interview coding problems/challenges

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.
Submitted by Divyansh Jaipuriyar, on September 03, 2020

Problem statement

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.

Solution Approach

(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