<p>Given a rectangle of size <code>n</code> x <code>m</code>, return <em>the minimum number of integer-sided squares that tile the rectangle</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/10/17/sample_11_1592.png" style="width: 154px; height: 106px;" /></p>

<pre>
<strong>Input:</strong> n = 2, m = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> <code>3</code> squares are necessary to cover the rectangle.
<code>2</code> (squares of <code>1x1</code>)
<code>1</code> (square of <code>2x2</code>)</pre>

<p><strong class="example">Example 2:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/10/17/sample_22_1592.png" style="width: 224px; height: 126px;" /></p>

<pre>
<strong>Input:</strong> n = 5, m = 8
<strong>Output:</strong> 5
</pre>

<p><strong class="example">Example 3:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/10/17/sample_33_1592.png" style="width: 224px; height: 189px;" /></p>

<pre>
<strong>Input:</strong> n = 11, m = 13
<strong>Output:</strong> 6
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n, m &lt;= 13</code></li>
</ul>

class Solution:
    def tilingRectangle(self, n: int, m: int) -> int:
        if n == 1:
            return m

        tiles = []
        for i in range(m):
            tiles.append([])

        def is_full(tiles):
            full = True

            for vertex in tiles:
                if sum(vertex) != n:
                    full = False

            return full

        def is_valid(tiles, index, square):
            if index + square > m:
                return False

            valid = True

            current_len = sum(tiles[index])

            for i in range(index, index + square - 1):
                if sum(tiles[i]) != current_len:
                    valid = False

            return valid

        def dfs(tiles, min_squares, squares):
            if is_full(tiles):
                return min(min_squares, squares)

            if squares >= min_squares:
                return min_squares

            min_index = 0
            min_len = n + 1

            for index in range(m):
                lens = sum(tiles[index])
                if lens < min_len:
                    min_len = lens
                    min_index = index

            for square in range(min(n - min_len, m - min_index), 0, -1):
                if is_valid(tiles, min_index, square):
                    for i in range(min_index, min_index + square):
                        tiles[i].append(square)

                    min_squares = min(min_squares, dfs(tiles, min_squares, squares + 1))

                    for i in range(min_index, min_index + square):
                        tiles[i].pop()
                        
            return min_squares

        return dfs(tiles, n * m, 0)



250