<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:

        def fill_missing(a: List[List[int]], n: int, ra: int) -> int:
            c = 0
            if n > 0:
                while ra > 0:
                    b = min(ra, n)
                    t = ra // b
                    # Multiple adjacent squares of same size
                    # can be treated as a rectangle of width b * t and height b
                    a.append([b * t, b])
                    ra -= b * t
                    c += t
            return c

        def find_rects_count(n, m, initial) -> int:
            a = [ [initial, initial] ]

            cnt = 1 + fill_missing(a, n, m - initial)
            
            while n > 0:
                min_n = min( x[1] for x in a )
                ra = m
                for i, item in zip(itertools.count(len(a)-1, -1), reversed(a)):
                    item[1] -= min_n
                    if item[1] == 0:
                        a[i]=a[-1]
                        a.pop()
                    else:
                        ra -= item[0]
                n -= min_n
                cnt += fill_missing(a, n, ra)

            return cnt
            
        boundary = min(n, m)
        r = n * m
        for b in range(boundary//2, boundary+1):
            r = min(r, find_rects_count(n, m, b))

        return r
16500