<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:
    // Class variables to store cost matrix, sizes of groups, and memoization table
    vector<vector<int>> cost;
    int size1, size2;
    int dp[13][1 << 12];  // Memoization table: dp[i][mask] (for each point i in Group A and mask for Group B)
    
    // Recursive function to calculate the minimum cost
    int minCost(int i, int mask) {
        // Base case: if all points in Group A are connected
        if (i == size1) {
            // We need to ensure all points in Group B are connected
            int extraCost = 0;
            // Loop through Group B to check if any point is not connected
            for (int j = 0; j < size2; ++j) {
                if (!(mask & (1 << j))) {  // If point j in Group B is not connected
                    // Find the minimal cost to connect this point j
                    int minConnectionCost = INT_MAX;
                    for (int k = 0; k < size1; ++k) {
                        minConnectionCost = min(minConnectionCost, cost[k][j]);
                    }
                    extraCost += minConnectionCost;  // Add the minimum cost to connect j
                }
            }
            return extraCost;
        }

        // Check if we have already computed this state
        if (dp[i][mask] != -1) {
            return dp[i][mask];
        }

        // Initialize the result as a large number (infinity)
        int result = INT_MAX;
        
        // Try connecting point i from Group A to each point j in Group B
        for (int j = 0; j < size2; ++j) {
            // Create a new mask to mark point j in Group B as connected
            int newMask = mask | (1 << j);
            // Recursively connect the next point in Group A and accumulate the cost
            result = min(result, cost[i][j] + minCost(i + 1, newMask));
        }
        
        // Memoize the result for this state
        return dp[i][mask] = result;
    }

    // Main function to calculate the minimum cost of connecting the two groups
    int connectTwoGroups(vector<vector<int>>& cost) {
        // Initialize class variables
        this->cost = cost;
        size1 = cost.size();
        size2 = cost[0].size();
        
        // Initialize memoization table with -1 (unvisited state)
        memset(dp, -1, sizeof(dp));
        
        // Start the recursion from point 0 in Group A and with no points connected in Group B (mask = 0)
        return minCost(0, 0);
    }
};
10400