1240. Tiling a Rectangle with the Fewest Squares

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

• Time : O(nm * min(n,m))
• Space : O(2^(n+m))

c++

class Solution {
    unordered_map<bitset<169>, int> visit;
    bool check(int y, int x, int width, int n, int m, bitset<169> bi) {
        if(y + width - 1 >= n) return false;
        if(x + width - 1 >= m) return false;
        for(int i = x; i < x + width; i++) {
            if(bi[i + (y + width - 1) * m]) return false;
        }
        for(int i = y; i < y + width; i++) {
            if(bi[x + width - 1 + i * m]) return false;
        }
        return true;
    }
    void change(int y, int x, int width, int m, bitset<169>& bi) {
        bi;
        for(int i = x; i < x + width; i++) {
            bi[i + (y + width - 1) * m] = 1;
        }
        for(int i = y; i < y + width; i++) {
            bi[x + width - 1 + i * m] = 1;
        }
        return ;
    }
    int solution(int &n, int &m, bitset<169> bi) {
        if(visit.count(bi)) return visit[bi];
        int res = INT_MAX;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                int p = j + i * m;
                if(bi[p]) continue;
                bitset<169> next = bi;
                for(int target = 1; target <= min(n,m) and check(i,j,target,n,m,next); target++) {
                    change(i,j,target,m,next);
                    res = min(res, solution(n,m, next) + 1);
                }
                return visit[bi] = res;
            }
        }
        return -1;
    }
public:
    int tilingRectangle(int n, int m) {
        if(n == m) return 1;
        if(n == 1 or m == 1) return max(n,m);
        bitset<169> bi;
        for(int i = 0; i < n*m; i++) {
            bi.flip(i);
        }
        visit[bi] = 0;
        for(int i = 0; i < n*m; i++) {
            bi.flip(i);
        }
        return solution(n,m, bi);
    }
};