Matrix and combination

Last Updated on March 29, 2022 by Ria Pathak

CONCEPTS USED:

Recursion

DIFFICULTY LEVEL:

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.

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);
  }
}

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)

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