<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 helper(int i, int flag, int bitmask, vector<vector<int>>& cost, vector<vector<vector<int>>>& dp) {
        int n = cost.size();
        int m = cost[0].size();
        
        // Base case: all rows processed
        if (i >= n) {
            // Check if all points in the second group are connected
            if (bitmask == (1 << m) - 1) {
                return 0;
            }
            return 1e6;  // Large number to indicate invalid state
        }
        
        // Memoization check
        if (dp[i][flag][bitmask] != -1) {
            return dp[i][flag][bitmask];
        }
        
        int ans = 1e6;  // Initialize with large number
        
        // Try connecting the i-th point in the first group to points in the second group
        for (int j = 0; j < m; j++) {
            if (bitmask & (1 << j)) {
                // If the point is already connected, skip further connections when flag == 1
                if (flag == 1) {
                    continue;
                }
                // Keep the connection as is and move to the next row
                ans = min(ans, cost[i][j] + helper(i + 1, 0, bitmask, cost, dp));
            } else {
                // Connect the point and try both options: continuing in the same row or moving to the next
                ans = min(ans, min(
                    cost[i][j] + helper(i, 1, bitmask | (1 << j), cost, dp),  // Stay in the same row
                    cost[i][j] + helper(i + 1, 0, bitmask | (1 << j), cost, dp)  // Move to the next row
                ));
            }
        }
        
        return dp[i][flag][bitmask] = ans;  // Store result in dp array
    }
    
    int connectTwoGroups(vector<vector<int>>& cost) {
        // 3D dp array initialized to -1
        vector<vector<vector<int>>> dp(cost.size() + 1, vector<vector<int>>(2, vector<int>(1 << cost[0].size(), -1)));
        return helper(0, 0, 0, cost, dp);
    }
};

14400