<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:
    def connectTwoGroups(self, cost: List[List[int]]) -> int:
        # groups of size s1 and s2
        # cost[i][j] is cost of i in group 1 to j of group 2

        # groups are connected if each point in both groups is connected to 1+ points in the other

        # so bipartite graph, but the graph can have disjoint components

        # greedy: pick the cheapest edge for each node
        # so we'd basically do Kruskal
        # update: I did Kruskal, calling the edges cost cost[u][v] / d
        # where d is the number of unconnected nodes among u and v. So half cost if neither, full cost if either,
        # inf cost if both already connected (so we don't take such nodes)

        # but that greedy algorithm is slightly wrong

        # time for super brute force:
        #   suppose we still need to connect u in group 1
        #     for each edge from u to node v in group 2:
        #     clear bit u and v and continue
        # return min cost

        L = len(cost)
        R = len(cost[0])

        allLeft = (1 << L) - 1
        
        minL = [min(cost[l][r] for r in range(R)) for l in range(L)]

        @cache
        def minCost(lmask, v) -> int:
            # the REAL optimization: wlog we need to connect every right node to a left node
            # brute force: try ALL the ways
            # for each next right node v:
            #    for each left node u:
            #       take edge u--v at cost cost[u][v]
            #       get the min cost to connect r+1: to the remaining left nodes
            #       record the unconnected left nodes in a bit set

            if v == R:
                return sum(minL[u] for u in range(L) if (1<<u) & lmask) # add lowest cost for all disconnected lefts

            # for each u in 0..L-1:
            #    take edge u--v, clear u's bit in lmask, continue with v+1
            return min(cost[u][v] + minCost(lmask & (allLeft ^ (1<<u)), v+1) for u in range(L))

        # prior solution: for each set left and right bit, I iterated over all edges
        # and cached `minCost(lmask, rmask)`. That was 2**24 states and O(L*R) work per state
        # which was way too expensive

        # this complexity, using the fact that there are more lefts than rights and thus
        # we can just iterate over rights
        #    For r rights taken thus far, lmask has (L choose 1) + ... + (L choose r) possible states.
        #    That's O(2**L) for L ~ r
        #    And there are O(R) of these, for O(2**L * R) states total
        #    and in each of those, it's O(L) work to iterate over the edges we can take
        #    So O(2**L * L * R) as the upper bound. Oof.
        #    Better than the prior bound of O(2**(L+R)*L*R)!
        #    And the cost will be a LOT lower than that bound if R << L, especially if R < L/2
        #    where L choose r will be a LOT smaller than 2**L
        
        return minCost(allLeft, 0)
42000