Problem statement

https://leetcode.com/problems/minimum-cost-to-connect-two-groups-of-points/

Solution 1

First, there is solution with O(3^n * n * m) time complexity. The idea is to keep state dp(i, mask), where i is number of points we traversed for left set of points and mask is binary mask of points used from the left side. Then when we take new point we need to calculate all possible submasks of mask and update dp(i, mask). For this we need to precalculate sums for each subset of n elements on the right and each of m elements on the left (with O(2^n * n * m) complexity is enough) Note also that we can keep empty set as well, but in this case we need to still add edge with minimum weight.

Complexity

Time complexity is O(3^n * n * m), space is O(2^n * n * m)

Code

class Solution:
    def connectTwoGroups(self, cost):
        m, n = len(cost), len(cost[0])
        sums = [[0]*(1<<n) for _ in range(m)]
        for i in range(m):
            for mask in range(1<<n):
                for bit in range(n):
                    sums[i][mask] += cost[i][bit] * ((mask>>bit) & 1)
            sums[i][0] = min(cost[i])

        @lru_cache(None)
        def dp(i, mask):
            if i == -1: return mask*1000
            ans = float("inf")
            submask = mask
            while submask:
                ans = min(ans, dp(i-1, mask^submask) + sums[i][submask])
                submask = (submask-1) & mask
            ans = min(ans, dp(i-1, mask) + sums[i][0])
            return ans
        
        return dp(m-1, (1<<n) - 1)

Solution 2

The idea is that for each point from left set we draw connection to the right set and then what we need to do is to add missing connections for the right part: we need to take the edges with the smallest values.

Complexity

Time complexity is O(2^n * n * m), space is O(2^n * n * m).

Code

class Solution:
    def connectTwoGroups(self, C):
        m, n = len(C), len(C[0])
        mins = [min(x) for x in zip(*C)]
        
        @lru_cache(None)
        def dfs(i, mask):
            if i == -1:
                return sum(mins[j] * ((mask>>j) & 1) for j in range(n))
            else:
                return min(C[i][j] + dfs(i-1, mask & ~(1<<j)) for j in range(n))

        return dfs(m-1, (1<<n) - 1)

Remark

There is also O(n^3) time complexity algorithm, we can lead it to minimum-cost edge cover problem for bipartite graph, which can be solved with matching problem with Hungarian algorithm.