<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)
    {
        // constants for storing size
        int n = cost.size();
        int m = cost[0].size();
        // cache table storing mask for size1 and index for size2
        vector<vector<int>> dp( m+1 , vector<int>( (1<<n) , -1) );

        // when all of size2 gets matched we will match unmatched members of size1 or group1
        // with size2 group greedily
        // so storing for current member in group1 what is minimum cost for a match in group2
        vector<int>mincost(n,110);

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                mincost[i] =  min(mincost[i],cost[i][j]);    
            }
        }
        // function
        function<int(int,int)> recur = [&](int index,int mask)
        {
            //  if all of group1 and group2 gets matched
            if(mask == ((1<<n)-1) and index == m)
            {
                return 0;
            }
            // base case already smaller size is matched so match unmatched greedily
            if(index == m)
            {

                int c = 0 ;
                for(int i=0;i<n;i++)
                {
                    if(! (mask & (1<<i)))
                    {
                        c+=  mincost[i];
                    }
                }
                return c;
            }
            // cache check
            if(dp[index][mask]!=-1)
            {
                return dp[index][mask];
            }
            // compute
            int ans = 1e9;
            for(int i=0;i<n;i++)
            {
                // match i in group1 with index in group2 
                
                    int new_mask = mask | (1<<i);
                    ans = min(ans, cost[i][index] + recur(index+1, new_mask) );  
                              
            }
            // save and return;
            return dp[index][mask] = ans;
        };
        return recur(0,0);
    }
};
16100