Tiling a Rectangle with the Fewest Squares

Problem

Given a rectangle of size n x m, return the minimum number of integer-sided squares that tile the rectangle.

Examples

Example 1

1
2
3
4
5
6
7
8



![](https://assets.leetcode.com/uploads/2019/10/17/sample_11_1592.png)

Input: n = 2, m = 3
Output: 3
Explanation: 3 squares are necessary to cover the rectangle.
2 (squares of 1x1)
1 (square of 2x2)

Example 2

1
2
3
4
5



![](https://assets.leetcode.com/uploads/2019/10/17/sample_22_1592.png)

Input: n = 5, m = 8
Output: 5

Example 3

1
2
3
4
5



![](https://assets.leetcode.com/uploads/2019/10/17/sample_33_1592.png)

Input: n = 11, m = 13
Output: 6

Constraints

1 <= n, m <= 13

Solution

Method 1 – Backtracking with Pruning

Intuition

Try to fill the rectangle greedily with the largest possible square at each step, backtracking and pruning when the current path cannot improve the best answer found so far.

Approach

Use DFS/backtracking. At each step, find the first empty cell, try all possible square sizes, fill, recurse, and backtrack. Prune if the current count exceeds the best found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int res = INT_MAX;
    int tilingRectangle(int n, int m) {
        vector<vector<int>> rect(n, vector<int>(m));
        dfs(rect, 0);
        return res;
    }
    void dfs(vector<vector<int>>& rect, int cnt) {
        int n = rect.size(), m = rect[0].size();
        if (cnt >= res) return;
        int x = -1, y = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (rect[i][j] == 0) {
                    x = i; y = j;
                    goto found;
                }
            }
        }
        res = min(res, cnt);
        return;
    found:
        int maxLen = min(n - x, m - y);
        for (int k = maxLen; k >= 1; --k) {
            bool canFill = true;
            for (int i = 0; i < k && canFill; ++i)
                for (int j = 0; j < k && canFill; ++j)
                    if (rect[x + i][y + j]) canFill = false;
            if (!canFill) continue;
            for (int i = 0; i < k; ++i)
                for (int j = 0; j < k; ++j)
                    rect[x + i][y + j] = 1;
            dfs(rect, cnt + 1);
            for (int i = 0; i < k; ++i)
                for (int j = 0; j < k; ++j)
                    rect[x + i][y + j] = 0;
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


import java.util.*;
public class Solution {
    private int res = Integer.MAX_VALUE;
    public int tilingRectangle(int n, int m) {
        int[][] rect = new int[n][m];
        dfs(rect, 0);
        return res;
    }
    private void dfs(int[][] rect, int cnt) {
        int n = rect.length, m = rect[0].length;
        if (cnt >= res) return;
        int x = -1, y = -1;
        outer:
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (rect[i][j] == 0) {
                    x = i; y = j;
                    break outer;
                }
            }
        }
        if (x == -1) {
            res = Math.min(res, cnt);
            return;
        }
        int maxLen = Math.min(n - x, m - y);
        for (int k = maxLen; k >= 1; --k) {
            boolean canFill = true;
            for (int i = 0; i < k && canFill; ++i)
                for (int j = 0; j < k && canFill; ++j)
                    if (rect[x + i][y + j] != 0) canFill = false;
            if (!canFill) continue;
            for (int i = 0; i < k; ++i)
                for (int j = 0; j < k; ++j)
                    rect[x + i][y + j] = 1;
            dfs(rect, cnt + 1);
            for (int i = 0; i < k; ++i)
                for (int j = 0; j < k; ++j)
                    rect[x + i][y + j] = 0;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


class Solution:
    def tilingRectangle(self, n: int, m: int) -> int:
        self.res = n * m
        rect = [[0] * m for _ in range(n)]
        def dfs(cnt):
            if cnt >= self.res:
                return
            for i in range(n):
                for j in range(m):
                    if rect[i][j] == 0:
                        x, y = i, j
                        break
                else:
                    continue
                break
            else:
                self.res = min(self.res, cnt)
                return
            max_len = min(n - x, m - y)
            for k in range(max_len, 0, -1):
                can_fill = True
                for dx in range(k):
                    for dy in range(k):
                        if rect[x + dx][y + dy]:
                            can_fill = False
                            break
                    if not can_fill:
                        break
                if not can_fill:
                    continue
                for dx in range(k):
                    for dy in range(k):
                        rect[x + dx][y + dy] = 1
                dfs(cnt + 1)
                for dx in range(k):
                    for dy in range(k):
                        rect[x + dx][y + dy] = 0
        dfs(0)
        return self.res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


impl Solution {
    pub fn tiling_rectangle(n: i32, m: i32) -> i32 {
        fn dfs(rect: &mut Vec<Vec<i32>>, cnt: i32, res: &mut i32) {
            let n = rect.len();
            let m = rect[0].len();
            if cnt >= *res { return; }
            let mut x = None;
            let mut y = None;
            'outer: for i in 0..n {
                for j in 0..m {
                    if rect[i][j] == 0 {
                        x = Some(i); y = Some(j);
                        break 'outer;
                    }
                }
            }
            if x.is_none() {
                *res = cnt.min(*res);
                return;
            }
            let x = x.unwrap();
            let y = y.unwrap();
            let max_len = n.min(m).min(n - x).min(m - y);
            for k in (1..=max_len).rev() {
                let mut can_fill = true;
                'check: for dx in 0..k {
                    for dy in 0..k {
                        if rect[x + dx][y + dy] != 0 {
                            can_fill = false;
                            break 'check;
                        }
                    }
                }
                if !can_fill { continue; }
                for dx in 0..k {
                    for dy in 0..k {
                        rect[x + dx][y + dy] = 1;
                    }
                }
                dfs(rect, cnt + 1, res);
                for dx in 0..k {
                    for dy in 0..k {
                        rect[x + dx][y + dy] = 0;
                    }
                }
            }
        }
        let n = n as usize;
        let m = m as usize;
        let mut rect = vec![vec![0; m]; n];
        let mut res = (n * m) as i32;
        dfs(&mut rect, 0, &mut res);
        res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


function tilingRectangle(n: number, m: number): number {
    let res = n * m;
    const rect = Array.from({ length: n }, () => Array(m).fill(0));
    function dfs(cnt: number) {
        if (cnt >= res) return;
        let x = -1, y = -1;
        outer: for (let i = 0; i < n; ++i) {
            for (let j = 0; j < m; ++j) {
                if (rect[i][j] === 0) {
                    x = i; y = j;
                    break outer;
                }
            }
        }
        if (x === -1) {
            res = Math.min(res, cnt);
            return;
        }
        let maxLen = Math.min(n - x, m - y);
        for (let k = maxLen; k >= 1; --k) {
            let canFill = true;
            for (let dx = 0; dx < k && canFill; ++dx) {
                for (let dy = 0; dy < k && canFill; ++dy) {
                    if (rect[x + dx][y + dy]) canFill = false;
                }
            }
            if (!canFill) continue;
            for (let dx = 0; dx < k; ++dx)
                for (let dy = 0; dy < k; ++dy)
                    rect[x + dx][y + dy] = 1;
            dfs(cnt + 1);
            for (let dx = 0; dx < k; ++dx)
                for (let dy = 0; dy < k; ++dy)
                    rect[x + dx][y + dy] = 0;
        }
    }
    dfs(0);
    return res;
}

Complexity

⏰ Time complexity: O((nm)!) (worst case, but pruned heavily)
🧺 Space complexity: O(nm)

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Backtracking with Pruning#

Intuition#

Approach#

Code#

Complexity#