Leetcode: 1240. Tiling a Rectangle with the Fewest Squares

Mistake: Overcomplicated solution. My Backtracking had the current square size to paint what made the solution too complicated.
Can we use brute-force to solve the problem? For each cell of the rectangle, for each possible square that can have its top-left corner on that cell, fill the area and move to the next empty cell on the same line. If there is no empty line in the line, continue the Backtracking on the next row. Time complexity is \(O(n \times m \times k^3)\) and space is \(O(n \times m)\).

class Solution:
    def tilingRectangle(self, n: int, m: int) -> int:
        grid = [[0] * m for _ in range(n)]

        ans = n * m

        def bt(i, j, cur):
            nonlocal ans
            if cur >= ans:
                return
            if i == n:
                ans = min(ans, cur)
                return
            while j < m and grid[i][j] > 0:
                j += 1
            if j == m:
                bt(i + 1, 0, cur)
                return
            for k in range(min(n - i, m - j), 0, -1):
                valid = True
                for ii in range(i, i + k):
                    for jj in range(j, j + k):
                        if grid[ii][jj] > 0:
                            valid = False
                        grid[ii][jj] += 1
                if valid:
                    bt(i, j + k, cur + 1)
                for ii in range(i, i + k):
                    for jj in range(j, j + k):
                        grid[ii][jj] -= 1

        bt(0, 0, 0)
        return ans


assert Solution().tilingRectangle(2, 3) == 3
assert Solution().tilingRectangle(5, 8) == 5
assert Solution().tilingRectangle(11, 13) == 6