Print all unique paths from a given source to destination in a Matrix moving only down or right

Implementation in C++

// C++ program to Print all unique paths from given source to destination in a Matrix moving only down or right
#include <bits/stdc++.h>
using namespace std;

vector<vector < int>> mat;
vector<int> s;
vector<int> d;
int m = 2, n = 3;

// Function to print all possible paths from given source to given destination  
void printVector(vector<int> path)
{
	int cnt = path.size();
	for (int i = 0; i < cnt; i += 2)
		cout << mat[path[i]][path[i + 1]] <<
		" ";
	cout << endl;
}

// Function to find all possible paths using recursion
void countPaths(int i, int j, vector<int> path)
{

	// Base Case
	if (i > d[0] || j > d[1])
		return;
	path.push_back(i);
	path.push_back(j);

	// When destination is reached
	if (i == d[0] && j == d[1])
	{
		printVector(path);
		return;
	}

	// Recursion
	countPaths(i, j + 1, path);
	countPaths(i + 1, j, path);
}

int main()
{
	mat = {
		{ 1, 2, 3 },
		{ 4, 5, 6 }
	};
	s = { 0, 0 };
	d = { 1, 2 };
	vector<int> path;

	countPaths(s[0], s[1], path);
	return 0;
}

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

Run Code

Output

Sample Input: 
1 2 3
4 5 6
0,0
1,2
Sample Output:
1 2 3 6
1 2 5 6
1 4 5 6

Complexity Analysis

Time Complexity: O(2^(n+m)).

Analysing Time Complexity:

Since matrix consists of n+m elements and each element has 2 possibilities.

Space complexity: O(1).

Frequently Asked Questions

1. When to use the backtracking method?
   Answer) Whenever there is some kind of decisive problem, we use the backtracking method.
    
2. What is recursion? 
   Answer) The calling function itself, again and again, is referred to as recursion. To know more about recursion, click here.
    
3. When to use recursion?
   Answer) When we can break the problem into smaller parts, we can use recursion. It also helps in reducing the complexity sometimes. 

Key Takeaways

This article taught us how to Print all unique paths from a given source to destination in a Matrix moving only down or right by approaching the problem using recursion and backtracking. We discussed its implementation using illustrations, pseudocode, and then proper code.

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

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

It's not the end. Must solve the problem of similar types. 

Recommended Problems:

• Unique Paths
• Longest Path Directed Acyclic Graph
• Longest Path In A Tree
• Aggressive Cows
   

Happy Coding.