HardNo. 1240
Tiling a Rectangle with the Fewest Squares — LeetCode 1240 Python Solution
- Pattern
- Backtracking
- Topics
- Backtracking
- Reading time
- 6 min
- Source
- leetcode.com
The problem
Given a rectangle of size n x m, return the minimum number of integer-sided squares that tile the rectangle.
Example
- Input
- n = 2, m = 3
- Output
- 3
- Explanation
- 3 squares are necessary to cover the rectangle.
Python solution
class Solution:
def tilingRectangle(self, n: int, m: int) -> int:
def dfs(i: int, j: int, t: int):
nonlocal ans
if j == m:
i += 1
j = 0
if i == n:
ans = t
return
if filled[i] >> j & 1:
dfs(i, j + 1, t)
elif t + 1 < ans:
r = c = 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 = r if r < c else c
for w in range(1, mx + 1):
for k in range(w):
filled[i + w - 1] |= 1 << (j + k)
filled[i + k] |= 1 << (j + w - 1)
dfs(i, j + w, t + 1)
for x in range(i, i + mx):
for y in range(j, j + mx):
filled[x] ^= 1 << y
ans = n * m
filled = [0] * n
dfs(0, 0, 0)
return ansComplexity
- Time
- Exponential (worst case)
- Space · auxiliary
- O(depth)
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1240. Tiling a Rectangle with the Fewest Squares is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1239 | Maximum Length of a Concatenated String with Unique Characters | Medium |
| 1238 | Circular Permutation in Binary Representation | Medium |
| 0039 | Combination Sum | Medium |
| 0040 | Combination Sum II | Medium |
| 0046 | Permutations | Medium |
| 0047 | Permutations II | Medium |
Frequently asked questions
- How hard is LeetCode 1240. Tiling a Rectangle with the Fewest Squares?
LeetCode 1240. Tiling a Rectangle with the Fewest Squares is rated Hard on LeetCode.
- What topics does LeetCode 1240. Tiling a Rectangle with the Fewest Squares cover?
LeetCode 1240. Tiling a Rectangle with the Fewest Squares is tagged Backtracking on LeetCode.