Given a grid of length m * n & different shapes (rectangle, square or L shape), return true if by picking all the shapes can it be made fit into the m * n grid without gaps.

The given shapes are allowed to be rotate multiple times or can also be fliped multiple times, we can perform any combination of rotation & flipping to make sure that the shapes are fitted on m * n grid without any gaps.

Decide the input to the function on your own, return type will be a boolean.

1. Rectange : 
    AA
    AA
    AA 

Example : 
    1. Rotating it by 90 degree 

    AAA
    AAA

	2. Rotating it by 180 degree 

	AA
	AA
	AA 

+Any combination of rotation or flipping. 

2. L shape 

    A
    A
    AA

    1. Flipping  
      A
      A
    A A

    2. Rotating it by 90 degree  

    AAA
    A

+Any combination of rotation or flipping. 

3. Same thing with square can be rotate or fliped, (Techinically doesn't matter with square it'll look same). 

Question 1 :

Let's say given input 4*4 matrix/grid and shapes as below  

L shape 

A
A
A 
A A 	

B 
B
BB

Sqaure 
C C 
C C 

Rectangle 
D D D 

The final result, hence return true. 
A D D D		
A C	C B
A C C B
A A B B

Ps - I came up with the approach where I said I'll perform a dfs on a matrix. I'll store the shapes in the map, where the key of the map will be the shape and the value of the map will be list of all possible premutation of that particular shape. Now apply the dfs try one shape from each key, if it any point there are gaps just backtrack & try different shape of that particular key.

Here I even said to the interveiwer that it's not necessary to make the shape fit the matrix since at the end we just have to return true or false.

I took some time for coding the solution, wasn't able to complete it in 45 mins, while coding it up there were some mishaps.
I have previously solved around 1000 questions on leetocede but still wasn't able to clear this round, I know the fact that the quality over quantity matters but sill, any feedback will be welcomed.