<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:
      # try brute force backtracking?
      board = [[0 for _ in range(n)] for _ in range(m)]

      ans = math.inf
      def bt(counts):
        nonlocal ans
        if counts >= ans:
          return
        
        pos = None
        found = False
        for row in range(m):
          for col in range(n):
            if board[row][col] == 0:
              pos = (row, col)
              found = True
              break
          if found:
            break
        if not found:
          ans = min(ans, counts)
          return

        # see how many difference size of squares we can place from this spot
        r, c = pos
        offset = 0
        while r + offset < m and c + offset < n and board[r + offset][c] == 0 and board[r][c + offset] == 0:
          offset += 1
        # max can place size is offset
        for row in range(r, r + offset):
          for col in range(c, c + offset):
            board[row][col] = 1
        # do bt and shrink
        while offset > 0:
          bt(counts + 1)
          # shrink
          for row in range(r, r + offset):
            board[row][c + offset - 1] = 0
          for col in range(c, c + offset):
            board[r + offset - 1][col] = 0
          offset -= 1

      bt(0)
      return ans
16600