<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 n,m;
    vector<vector<int>> v;
    vector<int> mini;
    int dp[1<<13][13];
    int f(int mask1,int ind){
        //BASE CASE : if we have explored all the indexe of set 2 and we are doing it to assign optimum values to set 1 members and a ind==-1 means every member of set 1 is assigned something 
        if(ind == -1){
            //Now we will be checking if there is anyone left to be paired in set 2 if yes then we will assign it the corresponding minimum values of set 1 from the mini vectors help
            int ans1 =0;
            for(int i=0;i<m;i++){
                if((mask1&(1<<i))==0){
                    ans1 += mini[i];
                }
            }
            // returning the calculated ans to the previous function calling
            //to be added in overall answer or we can say overall cost
            return ans1;
        }
        //MEMOIZATION
        if(dp[mask1][ind]!=-1)return dp[mask1][ind];

        int ans = INT_MAX;
        //Here we are setting each member of set 1 with optimal values in set 2
        //Means we are trying every values in set 2 for particular set 1 member who is at index ind .Also marking that set 2 member which is being assigned to set 1 member so that in base case we do not find its corresponding minimum cost in set 1
        for(int i=0;i<m;i++){
            ans = min(ans,v[ind][i] + f(mask1|(1<<i),ind-1));
        }
        return dp[mask1][ind]=ans;
    }
    int connectTwoGroups(vector<vector<int>>& cost) {
        v = cost;
        n = cost.size(),m=cost[0].size();
        mini.resize(m,INT_MAX);
        //Maintaining a mini vector containing all the minimum values of set 1
        memset(dp,-1,sizeof(dp));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                mini[j] = min(mini[j],cost[i][j]);
            }
        }
        return f(0,n-1);
    }
};
10900