Home » Interview coding problems/challenges

# Print all possible path from source to destination

Print all possible path from source to destination: The problem has been featured in interview/coding rounds of many companies such as Amazon, Citrix etc.

Submitted by Divyansh Jaipuriyar, on August 18, 2020

**Problem statement:**

You are given a matrix of the size of *N*M*, you need to print all the paths from top left to the bottom right of the given matrix. You can only move in right and down direction.

**Problem description:**

The problem wants you to find all the possible path from source(0,0) to destination(*N-1,M-1*) such that the path you follow must be either right or down from the previous point. i.e. *(i,j)->(i+1,j) and (i,j)->(i,j+1)*.

**Input:**

The first line of the input is the *T* number of test cases, each test case consists of two numbers *N* and *M* denoting the size of the matrix, following each of the *N* lines consists of *M* elements.

**Output:**

Print all the possible path from the top left to bottom right of the given matrix, print each path in a new line.

**Examples:**

Input: T=1 N=3,M=3 9 8 7 6 5 4 3 2 1 Output: Possible paths: 9 6 3 2 1 9 6 5 2 1 9 6 5 4 1 9 8 5 2 1 9 8 5 4 1 9 8 7 4 1

**Solution approach:**

The problem can be solved with the help of the backtracking concept. We will recursively check for the right movement and down movement from the current position each time, once we reached destination then we will print the path.

In order to check for each point in the matrix, we will use a visited array, if it is true then it means we have already visited or if it is false then we haven't visited it, if the given cell is already visited then we will simply skip it from the path and recur for another path.

For each position in the given matrix, we have two possibilities either it will be in the path or it will not be in the path. Once we reached the bottom right point then we will not return from it, we will print the path that has been used to reach the bottom end and again we check if is it possible to reach the bottom right from right of current position or from down of current position, if not then we will make the visited array false.

**Pseudo code:**

Here, mat[][] is the given matrix and vis[][] is Boolean matrix. void solve(mat[][],vis[][],x,y,n,m): { if index x and y out of bound then return . make vis[x][y]=true check if x==n-1 and y==n-1 if reached then print path. else recur for right recur for down make vis[x][y]=false again for further calls. }

**Time complexity** for the above approach is **exponential**.

**Space complexity** for the above approach is **O(N*M)**.

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; typedef long long ll; //declare solve function. void solve(vector<vector<ll> >& v1, vector<vector<bool> >& vis, ll x, ll y, ll n, ll m) { //check for index bound,if out of bound then //return from the function. if (x < 0 || x >= n || y < 0 || y >= m || vis[x][y] == true || v1[x][y] == 0) return; //make current node as visited. vis[x][y] = true; //check whether we reached //bottom right of matrix. if (x == n - 1 and y == m - 1) { //print path from top left //to bottom right. for (ll i = 0; i < n; i++) for (ll j = 0; j < m; j++) { //check if visited. if (vis[i][j]) cout << v1[i][j] << " "; } cout << "\n"; } //recursively move for down solve(v1, vis, x + 1, y, n, m); //recursively move for right. solve(v1, vis, x, y + 1, n, m); //once completed all moves from //current position make current node //as false and further backtracking calls. vis[x][y] = false; } 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; vector<vector<ll> > v1(n, vector<ll>(m)); vector<vector<bool> > vis(n, vector<bool>(m, false)); cout << "Enter elements:\n"; for (ll i = 0; i < n; i++) for (ll j = 0; j < m; j++) cin >> v1[i][j]; cout << "Possible paths:\n"; solve(v1, vis, 0, 0, n, m); } return 0; }

**Output:**

Enter number of test cases: 2 Enter size of matrix: 2 2 Enter elements: 4 5 6 7 Possible paths: 4 6 7 4 5 7 Enter size of matrix: 3 3 Enter elements: 9 8 7 6 5 4 3 2 1 Possible paths: 9 6 3 2 1 9 6 5 2 1 9 6 5 4 1 9 8 5 2 1 9 8 5 4 1 9 8 7 4 1

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions