<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 {
    int n, m;
    vector<bool> M;
    int ans;
    void backtrack(int y, int x, int cnt) {
        if(cnt > ans) return;
        if(y >= n) {
            ans = min(ans, cnt);
            return;
        }
        if(x >= m) {
            backtrack(y+1, 0, cnt);
            return;
        }
        if(M[y*m + x]) {
            backtrack(y, x+1, cnt);
            return;
        }
        int maxsz = min(n-y, m-x);
        int sz = 1;
        for(; y+sz<=n && x+sz<=m; sz++) {
            bool poss = true;
            for(int i=1; i<=sz; ++i) {
                if(M[(y+i-1)*m + x+sz-1] || M[(y+sz-1)*m + x+i-1]) {
                    poss = false;
                    break;
                }
            }
            if(!poss) break;

            for(int i=1; i<=sz; ++i)
                M[(y+i-1)*m + x+sz-1] = M[(y+sz-1)*m + x+i-1] = true;
        }
        while(--sz) {
            backtrack(y, x+sz, cnt+1);
            for(int i=1; i<=sz; ++i)
                M[(y+i-1)*m + x+sz-1] = M[(y+sz-1)*m + x+i-1] = false;
        }
    }
public:
    int tilingRectangle(int n, int m) {
        this->n = n;
        this->m = m;
        M.assign(n*m, 0);
        ans = max(n, m);
        backtrack(0, 0, 0);
        return ans;
    }
};
8600