Path exists in the matrix with the addition of element is at most K.

Implementation in C++

// C++ program to  Check if a path exists in the matrix with the addition of element is at most K.
#include <bits/stdc++.h>
using namespace std;

// Function to check validity on moving to the next index
bool validity(vector<vector<int>> &board, int i, int j, int K)
{
    if (board[i][j] <= K)
    {
        return true;
    }
    // else
    return false;
}

// Checking if a path exists from the given cell having coordinate (X, Y) of the matrix to any boundary cell with the sum of elements at most K.
bool findWay(vector<vector<int>> &board, int X, int Y, int M, int N, int K)
{
    if (X < 0 || X == M || Y < 0 || Y == N)
    {
        return true;
    }

    if (validity(board, X, Y, K))
    {
        // Storing the current element in a variable
        int board_XY = board[X][Y];

        // Marking the current(present) cell as visited
        board[X][Y] = INT_MAX;

        // Visiting all the adjacent cells and returning true
        if (findWay(board, X + 1, Y, M, N, K - board_XY) || findWay(board, X - 1, Y, M, N, K - board_XY) || findWay(board, X, Y + 1, M, N, K - board_XY) || findWay(board, X, Y - 1, M, N, K - board_XY))
        {
            return true;
        }

        // Marking the cell unvisited if above case does not hold.
        board[X][Y] = board_XY;
    }

    return false;
}

int main()
{
    vector<vector<int>> grid = {
        {2, 3, 4, 5},
        {1, 2, 3, 4},
        {1, 4, 5, 7}};

    int K;
    cin >> K;
    int M = grid.size();
    int N = grid[0].size();
    int X, Y;
    cin >> X >> Y;

    if (findWay(grid, X, Y, M, N, K))
        cout << "Yes";
    else
        cout << "No";

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Sample Input: 
6
1  2
Sample Output:
Yes

Complexity Analysis

Time Complexity: O(3^(N * M)).

Analysing Time Complexity:

The total number of elements in the matrix = N*M.

Each element has three directions to move.

Space complexity: O(N*M).

FAQs

1. What are boundary elements?
   Elements present in the leftmost, rightmost, topmost or bottommost side are boundary elements.
    
2. What are the different types of backtracking problems? 
   There are 3 different types of backtracking problems:
   (i) Decision problem-These problems demands for a feasible solution.
   (ii) Optimization problem-These problems demands for the best possible solution.
   (iii) Enumeration problem-These problems demands for all possible feasible solution.
    
3. Is backtracking the same as recursion?
   Recursion keeps on calling function till a base case is reached whereas backtracking uses a recursive approach to explore and exhaust all the possible results till we get the best result possible for the problem.

Key Takeaways

This article taught us to check if a path exists in the matrix with the addition of element is at most K by approaching the problem using the backtracking method. We discussed its implementation using illustrations, pseudocode and then optimised proper code.

We hope you could take away all critical techniques like analysing problems by walking over the execution of the examples and finding out the recursive pattern followed in most backtracking problems.

Check out this problem - Root To Leaf Path

Now, we recommend you practice problem sets based on backtracking to master your fundamentals. You can get a wide range of questions similar to this problem on CodeStudio