Matrix and combination

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 :

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

Output : ace acf ade adf bce bcf bde bdf

Explanation : 

Consider all combinations that start from a -
ace, acf, ade, adf
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:

Myself

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

Previous post Mike and Binary Number
Next post Range Even

Leave a Reply

Your email address will not be published. Required fields are marked *