<p>You are given a 2D <strong>binary</strong> array <code>grid</code>. You need to find 3 <strong>non-overlapping</strong> rectangles having <strong>non-zero</strong> areas with horizontal and vertical sides such that all the 1&#39;s in <code>grid</code> lie inside these rectangles.</p>

<p>Return the <strong>minimum</strong> possible sum of the area of these rectangles.</p>

<p><strong>Note</strong> that the rectangles are allowed to touch.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[1,0,1],[1,1,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">5</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/14/example0rect21.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 280px; height: 198px;" /></p>

<ul>
	<li>The 1&#39;s at <code>(0, 0)</code> and <code>(1, 0)</code> are covered by a rectangle of area 2.</li>
	<li>The 1&#39;s at <code>(0, 2)</code> and <code>(1, 2)</code> are covered by a rectangle of area 2.</li>
	<li>The 1 at <code>(1, 1)</code> is covered by a rectangle of area 1.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[1,0,1,0],[0,1,0,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">5</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/14/example1rect2.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 356px; height: 198px;" /></p>

<ul>
	<li>The 1&#39;s at <code>(0, 0)</code> and <code>(0, 2)</code> are covered by a rectangle of area 3.</li>
	<li>The 1 at <code>(1, 1)</code> is covered by a rectangle of area 1.</li>
	<li>The 1 at <code>(1, 3)</code> is covered by a rectangle of area 1.</li>
</ul>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= grid.length, grid[i].length &lt;= 30</code></li>
	<li><code>grid[i][j]</code> is either 0 or 1.</li>
	<li>The input is generated such that there are at least three 1&#39;s in <code>grid</code>.</li>
</ul>

class Solution:
    def minimumSum(self, grid: List[List[int]]) -> int:
        '''
        naive: 
            * for the current state, know where all the ones are.. 
            * among all the one positions, find the top left and bottom right corners..
            * if group == 1, this is the last group, just return the area

            * if group > 1, then I have groups yet to form... so try to cut somewhere horizontally, and between left and right..and solve each recursively.. (I know already where the top left and bottom right is at this point.. so easier to know where to start and end the cuts..)
            * for every possible cut, record the lowest area and return at each state..
            ====== works! => a bit slow, since it's trying out every possibility.. here's grid is at most 30.. so should be okay..  
            ====== hints suggest the same -> cut and try every possibility -> similar to lc 2312
        '''
        def helper(ones, groups): 
            if not ones: return 0 # no more ones left 

            l, r, t, b = inf, -inf, inf, -inf ### for the current set of ones.. find the top_left, and bottom_right corner.. 
            for i, j in ones: 
                l = min(l, j) # left min 
                r = max(r, j) # right max
                t = min(t, i) # top min 
                b = max(b, i) # max bottom.. 

            area = (b - t + 1) * (r - l + 1) # height * width 
            if groups == 1: # last group; no need to split anymore.. 
                return area 

            for cut_i in range(t, b): # cut somewhere between top and bottom and try it.. 
                one_part = set((i, j) for i, j in ones if i <= cut_i) # everything on or above
                other_part = ones - one_part # whatever is in ones.. that's not part of the above part.. 

                keep_one_part_intact = helper(one_part, 1) + helper(other_part, groups - 1) # form remainging groups in the other part.. 
                keep_other_part_intact = helper(other_part, 1) + helper(one_part, groups - 1) # form remaining groups in the first part.. 
                area = min(area, keep_one_part_intact, keep_other_part_intact)

            for cut_j in range(l, r): # cut somewhere between left and right and try it.. 
                one_part = set((i, j) for i, j in ones if j <= cut_j) # everything at or the left.. 
                other_part = ones - one_part # whatever is in ones.. that's not part of the left part.. 

                keep_one_part_intact = helper(one_part, 1) + helper(other_part, groups - 1) # form remainging groups in the other part.. 
                keep_other_part_intact = helper(other_part, 1) + helper(one_part, groups - 1) # form remaining groups in the first part.. 
                area = min(area, keep_one_part_intact, keep_other_part_intact)

            return area # return the min area at each state.. 


        init_ones_set = set()
        for i in range(len(grid)): 
            for j in range(len(grid[0])): 
                if grid[i][j] == 1: 
                    init_ones_set.add((i, j)) # put all the 1 positions into a set.. 

        return helper(init_ones_set, 3) # start with initial set of one positions and form 3 groups.. 
5888