## Introduction

In this blog, we will discuss a backtracking problem that has been asked frequently in Interviews.

The problem is to check if a path exists in the matrix with the addition of element is at most K.

Before we proceed, we must know what backtracking is?

Backtracking is an algorithmic technique for solving the recursive problem by building every possible solution incrementally and removing those answers that fail to satisfy the problemâ€™s constraints at any time.

Now letâ€™s look at the problem.

Recommended topic about, __kth largest element in an array__, and __Euclid GCD Algorithm__

### Problem Statement

We are given an M X N matrix, a coordinate, and a sum. We need to check for a path from the given coordinate to any boundary element of the matrix on the condition that the sum of the paths should not exceed the value K.

### Sample Example

Say, for example, our matrix of order 3 X 4 is given below:

Given coordinate = (1,2)

Sum = 6

The answer will be Yes because we can reach boundary element 1 at (1,0) position by moving from 3 to 2 and then to 1.

## Approach

Now to check if a path exists in the matrix with the addition of element is at most K, the following approach is followed.

Define a base case. Our base case will include the condition of whether our given coordinates are out of the matrix.

â¬‡

The sum given to us should be greater than the value at the coordinate given. If this exists then, follow the below steps.

â¬‡

Store the value of the coordinates given in a variable.

â¬‡

Mark the current cell as visited.

â¬‡

Start visiting all its adjacent cells and return true.

â¬‡

If the path does not exist, mark the cell unvisited and return false.

This is the most optimised approach using backtracking. The total number of elements in the matrix is N*M. Each element has three directions to move. Therefore, time complexity will be O(3^(N ** *M)) and space complexity will be O(N*M)

Till now, I guess you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try. __Coding Ninjas Studio__

If you were not able to solve it, donâ€™t be sad.

Please have a look at the algorithm, and then again, you must give it a try.

### PseudoCode

**Algorithm**

To check if a path exists in the matrix with the addition of element is at most K:

___________________________________________________________________

**procedure** findWay(vector<vector<int> >& board, int X, int Y, int M, int N, int K):

___________________________________________________________________

**1.** If X < 0 || X == M || Y < 0 || Y == N:

return true

**2**. if validity(board, X, Y, K):

board_XY = board[X][Y]

board[X][Y] = INT_MAX

**3.** if findWay(board, X + 1, Y, M, N, K - board_XY) or findWay(board, X - 1, Y, M, N, K - board_XY) or findWay(board, X, Y + 1, M, N, K - board_XY) or findWay(board, X, Y - 1, M, N, K - board_XY)): return true

**4.** board[X][Y] = board_XY;

**5. ** Return false

**6. end procedure**

___________________________________________________________________