Last Updated: 10 Apr, 2021
##### Minimum Cost To Connect Two Groups Of Points
Hard
Problem statement

#### Now you are supposed to find the minimum cost it takes to connect the two groups.

##### Input Format :
``````The first line contains an integer βTβ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains two integers βNβ and βMβ, denoting the number of rows and columns of the βcostβ matrix.

Each of the next βNβ lines contains βMβ space-separated integers denoting the elements of the βcostβ matrix.
``````
##### Output Format :
``````For each test case, print an integer denoting the minimum cost it takes to connect the two groups.

Print the output of each test case in a separate line.
``````
##### Note :
``````You are not required to print the expected output; it has already been taken care of. Just implement the function.
``````
##### Constraints :
``````1 <= T <= 5
1 <= N <= 10
1 <= M <= 10
0 <= cost[i][j] <= 100

Time limit: 1 sec
``````
Approaches

## 01Approach

Let us try to break down the problem into sub-problems. Consider a function

which returns the minimum cost to connect the first βidβ elements of group 1 to a subset of group 2 which is denoted by βmaskβ. Here, the βmaskβ is an integer whose jth bit (from Least significant bit) is set if the jth element (0th based indexing) of group 2 is already included in the subset.

Now, let us see what happens when we try to connect the id-th element of group 1 with some (one or more) elements of group 2. Weβll have to add the cost associated with the new connection and also weβll have to update the βmaskβ if a new element from group 2 is included.

Now, consider the following steps for implementing the function getMinCost():

1. Base Case:
• Check if βidβ is equal to -1.
• If βmaskβ is equal to (1 << M) - 1, which means every point of the second group is included in the connection. So, return 0.
• Otherwise, return a very large integer.
2. Initialise a βansβ variable with a very large integer which will store the result of the current function call.
3. Now, iterate through the points of the second group using the variable βjβ. These are the following two options possible.
• id-th element is connected to only one point from 2nd group. For this case: ans = min(ans,cost[id][j] + getMinCost(id - 1, mask | (1 << j))
• Id-th element is connected to more than one points from group 2 and j-th point is one of them. For this case, if jth bit is not set: ans = min(ans, cost[id][j] + getMinCost(id, mask | (1 << j))
4. Return βansβ.