# Matrix and combination

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 :

``````Input : [ [a, b],
[c, d],
[e, f] ]

Explanation :

Consider all combinations that start from a -
Consider all combinations that start from b -
bce, bcf, bde, bdf``````

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 by referring the best platform to learn data structures and algorithms.

#### 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.

#### Refer video for Quick Explaination: #### 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);
}
}
```