<p>You are given an <code>m x n</code> integer matrix <code>mat</code> and an integer <code>target</code>.</p>

<p>Choose one integer from <strong>each row</strong> in the matrix such that the <strong>absolute difference</strong> between <code>target</code> and the <strong>sum</strong> of the chosen elements is <strong>minimized</strong>.</p>

<p>Return <em>the <strong>minimum absolute difference</strong></em>.</p>

<p>The <strong>absolute difference</strong> between two numbers <code>a</code> and <code>b</code> is the absolute value of <code>a - b</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/03/matrix1.png" style="width: 181px; height: 181px;" />
<pre>
<strong>Input:</strong> mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13
<strong>Output:</strong> 0
<strong>Explanation:</strong> One possible choice is to:
- Choose 1 from the first row.
- Choose 5 from the second row.
- Choose 7 from the third row.
The sum of the chosen elements is 13, which equals the target, so the absolute difference is 0.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/03/matrix1-1.png" style="width: 61px; height: 181px;" />
<pre>
<strong>Input:</strong> mat = [[1],[2],[3]], target = 100
<strong>Output:</strong> 94
<strong>Explanation:</strong> The best possible choice is to:
- Choose 1 from the first row.
- Choose 2 from the second row.
- Choose 3 from the third row.
The sum of the chosen elements is 6, and the absolute difference is 94.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/03/matrix1-3.png" style="width: 301px; height: 61px;" />
<pre>
<strong>Input:</strong> mat = [[1,2,9,8,7]], target = 6
<strong>Output:</strong> 1
<strong>Explanation:</strong> The best choice is to choose 7 from the first row.
The absolute difference is 1.
</pre>

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

<ul>
	<li><code>m == mat.length</code></li>
	<li><code>n == mat[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 70</code></li>
	<li><code>1 &lt;= mat[i][j] &lt;= 70</code></li>
	<li><code>1 &lt;= target &lt;= 800</code></li>
</ul>

class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        R = len(mat)
        C = len(mat[0])

        # all entries positive which helps

        # minimize abs sum

        # DFS + backtracking with early pruning?

        # DP seems unlikely because numbers combine in surprising ways,
        # for current value x >> 1 we might want a prior value that's small,
        # and for x ~ 1 we want a prior value that's big

        # entries are in 1..70 which also helps a LOT

        # 70**3 is 3.4e5 so we can brute-force the set combinations; target is just 800 at most
        # so we can safely discard combinations above that number and just track the min of combos above;
        # the rest are irrelevant

        lowest = sum(min(row) for row in mat)
        if lowest >= target: return lowest-target

        prev = {0}

        for r in range(R):
            hi = math.inf # min sum >= target
            curr = set()
            for p in prev:
                for v in mat[r]:
                    if p + v < target:
                        curr.add(p+v)
                    else:
                        hi = min(hi, p+v)

            print(f"row {r=}: {sorted(curr)}")

            if r == R-1:
                return min(target-max(curr), hi-target)

            curr.add(hi) # FIXED: best solution might involve overshooting a bit in a prior row then adding a small last value
            prev = curr

        # O(target*C) in each inner loop
        # O(target*R*C) total
1678