## Introduction

In this blog, we will discuss a 2-D array problem asked frequently in Interviews.

The problem is to **Print all unique paths from a given source to destination in a Matrix moving only down or right.**

We are given an N X M matrix, a source coordinate and a destination coordinate. We need to print all possible paths to reach from source to destination.

Example: Say we have 2 X 3 matrix, source given is (0,0) and destination is (1,2)

We have to find all possible paths in which we can reach from source to destination.

Here we will get our answer as 3.

Also see, __kth largest element in an array__, and __Euclid GCD Algorithm__

## Approach

The** approach** to Print all unique paths from a given source to destination in a Matrix moving only down or right can be explained by the recursion method.

In our example, we have 2 X 3 matrix. Source = 0,0 and Destination = 1,2.

Define the base case. If the current cell is out of bound then simply return.

â¬‡

If the destination is reached, then return 1.

â¬‡

Call the recursive function two times, one for the down cell and the other for the right cell with respect to the current cell.

So the recursion tree would be:

Time Complexity = O(2^(n+m))

Space Complexity = O(1)

Till now, I assume 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: __Try here__

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

### PseudoCode

**Algorithm**

___________________________________________________________________

**procedure** countPaths(int i, int j, vector<int> path):

___________________________________________________________________

**1. **if i > d[0] || j > d[1]: return

**2.** path.push_back(i)

path.push_back(j)

**3.** if (i == d[0] && j == d[1]):

printVector(path);

return;

**4. **countPaths(i, j + 1, path);

countPaths(i + 1, j, path);

**end procedure**

___________________________________________________________________