Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Matrix and combination

Last Updated on March 29, 2022 by Ria Pathak

Recursion

Medium

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given a matrix `M`*`N` containing only lowercase english alphabets, your task is to select elements from the first row one by one, and print all the possible combinations downwards.

Conditions for making Combinations:
`Rule1-` Every combination starts from the first row of the matrix and proceeds downwards. He may switch columns though.
`Rule2-` Every combination should have characters equal to the number of rows.
`Rule3-` A combination can’t have an element from the same row present twice.

See original problem statement here

#### For Example :

Can we use `Recursion` here ?

Yes, as the problem demands to print all the possible combinations. We can use `Recursion` to find all such combinations.

### SOLVING APPROACH:

1. Initialize an empty string `Str` to store our resultant output.
2. Start traversing each and every row recursively by incrementing the value of `curr row` by `1` and keep appending the current character in the `Str`, when we reach the last row, print `Str` and return, as there are no values to process further.
3. Similarly all combinations of first row elements will be generated by following `step` `2`, `N` number of times in a loop.

### SOLUTIONS:

```
#include <bits/stdc++.h>
using namespace std;

void matrixAndComb(vector<vector<char>> v, int i, int m, int n, string str){

if(i == m){
cout<<str<<" ";
return ;
}

for(int j=0; j<n; j++)
matrixAndComb(v, i+1, m, n, str + v[i][j]);
}

int main()
{
int m,n; cin>>m>>n;
vector<vector<char> > v( m , vector<char> (n));
for(int i=0; i<m; i++){
for(int j=0; j<n; j++)
cin>>v[i][j];
}
string str = "";
matrixAndComb(v , 0, m, n, str);

return 0;
}
```
```import java.util.*;
import java.io.*;

public class Main {
static void matrixAndComb(char [][]arr, int i, int m, int n, String str){

/* if rows end print the string */
if(i == m){
System.out.print(str + " ");
return ;
}
for(int j=0; j<n; j++){

matrixAndComb(arr, i+1, m, n, str + arr[i][j]);
}
}

public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
char arr[][] = new char[m][n];
for(int i=0; i<m; i++){
for(int j=0; j<n; j++)
arr[i][j] = sc.next().charAt(0);
}
String str = "";
matrixAndComb(arr , 0, m, n, str);
}
}
```
```def matrixAndComb( v, i, m, n,  str):
if(i == m):
print(str, end = " ")
return

for j in range(n):
matrixAndComb(v, i+1, m, n, str + v[i][j])

m, n = map(int,input().split())
v = []

for i in range(m):
v.append(input().split())

str = ""
matrixAndComb(v, 0, m, n, str)
```

[forminator_quiz id="1004"]

This article tried to discuss the concept of Recursion. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming