2184. Number of Ways to Build Sturdy Brick Wall

You are given integers height and width which specify the dimensions of a brick wall you are building. You are also given a 0-indexed array of unique integers bricks, where the ith brick has a height of 1 and a width of bricks[i]. You have an infinite supply of each type of brick and bricks may not be rotated.

Each row in the wall must be exactly width units long. For the wall to be sturdy, adjacent rows in the wall should not join bricks at the same location, except at the ends of the wall.

Return the number of ways to build a sturdy wall. Since the answer may be very large, return it modulo 109 + 7.

class Solution {
    vector<vector<int>> combs;
    int mod = 1e9 + 7;
    void init(vector<int>& comb, vector<int>& b, int& w) {
        if(comb.back() == w) {
            combs.push_back(comb);
        } else {
            for(int& B : b) {
                if(comb.back() + B <= w) {
                    comb.push_back(comb.back() + B);
                    init(comb,b,w);
                    comb.pop_back();
                }
            }
        }
    }
    bool conn(vector<int>& b1, vector<int>& b2) {
        int i = 0, j = 0;
        while(i + 1 < b1.size() and j + 1 < b2.size()) {
            if(b1[i] == b2[j]) return false;
            if(b1[i] < b2[j]) i++;
            else j++;
        }
        return true;
    }
    vector<vector<int>> initGraph() {
        int n = combs.size();
        vector<vector<int>> g(n);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(conn(combs[i], combs[j])) {
                    g[i].push_back(j);
                }
            }
        }
        return g;
    }
    int helper(vector<vector<int>>& dp, vector<vector<int>>& g, int n, int c, int h) {
        if(c == h) return 1;
        if(dp[c][n] != -1) return dp[c][n];
        int& res = dp[c][n] = 0;
        for(auto near : g[n]) {
            res = (res + helper(dp,g,near,c+1,h)) % mod;
        }
        return res;
    }
public:
    int buildWall(int height, int width, vector<int>& bricks) {
        vector<int> tmp;
        for(auto& b : bricks) {
            if(b <= width) {
                tmp.push_back(b);
                init(tmp,bricks,width);
                tmp.pop_back();
            }
        }
        
        auto g = initGraph();
        vector<vector<int>> dp(height, vector<int>(combs.size(), -1));
        int res = 0;
        for(int i = 0; i < combs.size(); i++) {
            res = (res + helper(dp,g,i,1,height)) % mod;
        }
        return res;
    }
};