<p>You are given two groups of points where the first group has <code>size<sub>1</sub></code> points, the second group has <code>size<sub>2</sub></code> points, and <code>size<sub>1</sub> &gt;= size<sub>2</sub></code>.</p>

<p>The <code>cost</code> of the connection between any two points are given in an <code>size<sub>1</sub> x size<sub>2</sub></code> matrix where <code>cost[i][j]</code> is the cost of connecting point <code>i</code> of the first group and point <code>j</code> of the second group. The groups are connected if <strong>each point in both groups is connected to one or more points in the opposite group</strong>. In other words, each point in the first group must be connected to at least one point in the second group, and each point in the second group must be connected to at least one point in the first group.</p>

<p>Return <em>the minimum cost it takes to connect the two groups</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/03/ex1.jpg" style="width: 322px; height: 243px;" />
<pre>
<strong>Input:</strong> cost = [[15, 96], [36, 2]]
<strong>Output:</strong> 17
<strong>Explanation</strong>: The optimal way of connecting the groups is:
1--A
2--B
This results in a total cost of 17.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/03/ex2.jpg" style="width: 322px; height: 403px;" />
<pre>
<strong>Input:</strong> cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
<strong>Output:</strong> 4
<strong>Explanation</strong>: The optimal way of connecting the groups is:
1--A
2--B
2--C
3--A
This results in a total cost of 4.
Note that there are multiple points connected to point 2 in the first group and point A in the second group. This does not matter as there is no limit to the number of points that can be connected. We only care about the minimum total cost.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
<strong>Output:</strong> 10
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>size<sub>1</sub> == cost.length</code></li>
	<li><code>size<sub>2</sub> == cost[i].length</code></li>
	<li><code>1 &lt;= size<sub>1</sub>, size<sub>2</sub> &lt;= 12</code></li>
	<li><code>size<sub>1</sub> &gt;= size<sub>2</sub></code></li>
	<li><code>0 &lt;= cost[i][j] &lt;= 100</code></li>
</ul>

class Solution {
public:
    int connectTwoGroups(vector<vector<int>>& cost) {
        /*
        - ret min cost to connect 2 groups
        - every pt from first group must be connected to 1+ pts in second, and vice versa

        - 1 val from every row must be used and 1 val from every col
        - size <= 12
        - if u use any row more than once, means some col must be used more than once
        - recur
            - keep mask for rows and cols, fill which row or col is being used
            - b.c. is when all bits set to 1 (size bits, 12 max)

        - intuit: 
            - r0 -> pick min val = c0
            - r1 -> min val = c1, c2
            - r2 -> m.v. = c0
            - min combo is c0 in r2, then c1 and c2 in r1
            - only know this after seeing r2

        - ex3
            - r0=c2, r1=c0, r2=c1, r3=c1, r4=c0 -> 10

        - each row, choose btwn min val of unseen cols, or min val of seen calls if its < min unseen
        - so for 
        - once all rows r taken care of, look at useen cols, and choose min vals from them 
        - in r1, take min of choosing any row -- mark that row and col seen
            - mark seen my removing from unseen set, or using mask so we can dp it 
            - 2^n * 2^n = 2^2*n

        - or, lets say we sort each row and col
        r0: {1:0, 3:1, 5:2}, r1: {1:1, 1:2, 4:0}, r2: {1:0, 3:2, 5:1}
        c0: {1:0, 1:2, 4:1}, c1: {1:1, 3:0, 5:2}, c2: {1:1, 3:2, 5:0}

        - from here 

        - set k'th bit = ((1 << k) | n)
        */
        int n = cost.size();
        int m = cost[0].size();
        int mask_c_options = pow(2, m);
        vector<vector<vector<int>>> mc(n + 1, vector<vector<int>>(m + 1, vector<int>(mask_c_options + 1)));

        // each var deps on larger val -- fill in dec order
        for (int r = n; r >= 0; --r) {
            for (int c = m; c >= 0; --c) {
                for (int mask_c = mask_c_options; mask_c >= 0; --mask_c) {
                    if (r >= cost.size() && c >= cost[0].size()) {
                        mc[r][c][mask_c] = 0;
                    } else {
                        int curr_min = INT_MAX;
                        if (r < cost.size()) {
                            for (int i = 0; i < m; ++i) {
                                // update maskr & maskc
                                int tmp_mask_c = min(mask_c_options, mask_c | 1 << i);
                                // if (mc[r + 1][c][tmp_mask_r][tmp_mask_c] != INT_MAX) curr_min = min(curr_min, cost[r][i] + mc[r + 1][c][tmp_mask_r][tmp_mask_c]);
                                curr_min = min(curr_min, cost[r][i] + mc[r + 1][c][tmp_mask_c]);
                            }
                        } else {
                            // check if c alr chosen
                            if (mask_c & (1 << c)) {
                                curr_min = mc[r][c + 1][mask_c];
                            } else {
                                // choose min of this col
                                for (int i = 0; i < n; ++i) {
                                    // update maskr & maskc
                                    int tmp_mask_c = min(mask_c_options, mask_c | 1 << c);
                                    // if (mc[r][c + 1][tmp_mask_r][tmp_mask_c] != INT_MAX) curr_min = min(curr_min, cost[i][c] + mc[r][c + 1][tmp_mask_r][tmp_mask_c]);
                                    curr_min = min(curr_min, cost[i][c] + mc[r][c + 1][tmp_mask_c]);
                                }
                            }
                        }

                        mc[r][c][mask_c] = curr_min;
                        // cout << r << " " << c << " " << mask_r << " " << mask_c << " " << curr_min << endl; 
                    }
                }
            }
        }  

        return mc[0][0][0];

        // dont need r,c,r_mask,c_mask ... just need r and c_mask
        // return minCost(0, 0, 0, cost);
    }

    /*
    - first do r's till r reaches n
    - then do c's till c reaches m
    - if some c is in mask alr, then skip it
    - b.c. is when r and c r done
    - check bit n is set --> temp & (1 << N)


    - new w/ just r & c_mask:
    - b.c. is when r == n and c_mask is done
    - if r < n, then choose min of anything in that row
    - if c_mask not done, then see which bit is missing (go though all c < m)
        - then choose min val from that col 

    - 1:51
    
    - actually first try w/ r, c, mask_c ... cuz same time complexity as above i believe (since we dont loop through c in if cond)
    - dont need mask_r cuz we alr go through all r
    */
    // int minCost(int r, int c, int mask_c, vector<vector<int>>& cost) {
    //     // cout << r << " " << c << " " << mask_c << endl; 
    //     if (r >= cost.size() && c >= cost[0].size()) return 0;

    //     int mc = INT_MAX;
    //     if (r < cost.size()) {
    //         for (int i = 0; i < cost[0].size(); ++i) {
    //             // update maskr & maskc
    //             int tmp_mask_c = mask_c | 1 << i;
    //             mc = min(mc, cost[r][i] + minCost(r + 1, c, tmp_mask_c, cost));
    //         }
    //     } else {
    //         // check if c alr chosen
    //         if (mask_c & (1 << c)) return minCost(r, c + 1, mask_c, cost);

    //         // choose min of this col
    //         for (int i = 0; i < cost.size(); ++i) {
    //             // update maskr & maskc
    //             int tmp_mask_c = mask_c | 1 << c;
    //             mc = min(mc, cost[i][c] + minCost(r, c + 1, tmp_mask_c, cost));
    //         }
    //     }

    //     return mc;
    // }
};
32400