1240. Tiling a Rectangle with the Fewest Squares

Problem Description

Given a rectangle of size n x m, find the minimum number of integer-sided squares needed to tile the rectangle.

Solution: Recursive Backtracking with Bit Manipulation

This problem can be efficiently solved using recursive backtracking combined with bit manipulation for state representation. The key idea is to explore all possible ways to place squares within the rectangle, keeping track of the minimum number of squares used.

State Representation:

We use a bitmask to represent the state of each row. Each bit in the bitmask corresponds to a column in the rectangle. A 1 indicates that the column is covered by a square, and a 0 indicates it's uncovered. An array of n integers (one for each row) is used to store the row states.

Recursive Backtracking:

The backtracking function dfs(i, j, t) explores the rectangle row by row, column by column:

1. Base Case: If i == n, all rows are filled, so we've found a tiling. Update the minimum number of tiles (ans) and return.

2. Row Transition: If j == m, the current row is complete. Move to the next row (i + 1, 0).

3. Skip Covered Cells: If the current cell (i, j) is already covered (filled[i] >> j & 1), move to the next cell (i, j + 1).

4. Explore Square Sizes: Otherwise, find the largest possible square that can be placed at (i, j). This involves checking how many consecutive uncovered columns and rows are available starting from the current cell. The maximum side length mx is determined by the minimum of available rows and columns.

5. Place Squares: Iterate through possible square sizes (w from 1 to mx). For each size:

   • Update the filled array to mark the covered cells.
   • Recursively call dfs(i, j + w, t + 1) to explore the next part of the rectangle.
   • Crucially, backtrack: Clear the cells covered by the current square to explore other possibilities.

Time Complexity: The time complexity is exponential, O(nm * 2^(nm)) in the worst case because of the recursive exploration of all possible square placements. The actual runtime is significantly faster due to pruning (t + 1 < ans).

Space Complexity: O(n) for the filled array. The recursive call stack could also use O(n*m) in the worst case.

Code Implementation (Python)

class Solution:
    def tilingRectangle(self, n: int, m: int) -> int:
        ans = n * m
        filled = [0] * n
 
        def dfs(i, j, t):
            nonlocal ans
            if i == n:
                ans = t
                return
            if j == m:
                dfs(i + 1, 0, t)
                return
            if filled[i] >> j & 1:
                dfs(i, j + 1, t)
                return
            if t + 1 >= ans:
                return
 
            r, c = 0, 0
            for k in range(i, n):
                if filled[k] >> j & 1:
                    break
                r += 1
            for k in range(j, m):
                if filled[i] >> k & 1:
                    break
                c += 1
            mx = min(r, c)
            for w in range(1, mx + 1):
                for k in range(w):
                    filled[i + k] |= 1 << (j + w - 1)
                filled[i + w - 1] |= (1 << w) - 1 << j
                dfs(i, j + w, t + 1)
                for k in range(w):
                    filled[i + k] ^= 1 << (j + w - 1)
                filled[i + w - 1] ^= (1 << w) - 1 << j
 
        dfs(0, 0, 0)
        return ans

The code in other languages (Java, C++, Go, TypeScript) would follow a very similar structure, using bit manipulation and backtracking. The core logic remains consistent. Remember that the exponential nature of the solution makes it less efficient for significantly larger n and m values.