<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:
        # Top down dp
        # O(RC*RC) 3*3*3 or 4*4*4*4  O(RC*RC)

        # store the mxn size of the matrix
        R, C = len(mat), len(mat[0])
        #dp = defaultdict(defaultdict)
        
        # Sorting each row of the array for more efficient pruning
        # Note:this purely based on the observation on problem constraints (although interesting :))
        mat = [sorted(row) for row in mat] # RClogC
  
        
        # returns minimum absolute starting from from row i to n-1 for the target
        globalMin = float("inf")
        @cache
        def dp(r, cum):
            nonlocal globalMin
            
            if globalMin == 0:
                return
                
            if r == R:
                globalMin = min(globalMin, abs(cum-target))
                return abs(cum-target)
            
    
            # pruning step 1: because the array is increasing & prevSum & target will always be positive
            if cum-target > globalMin:
                return float("inf")
            

            res = float("inf") # not 0
            # for each candidate select that and backtrack
            for c in range(C):
                res = min(res, dp(r+1, cum + mat[r][c]))
                # pruning step 2 - break if we found minDiff 0 --> VERY CRTICIAL => the right elements => no meaning
                if res == 0: # no more as they are positive # found the best already # this work with sorted well
                    break
            return res
        
        return dp(0, 0)       

        """
        # Considerable
        # O(target *n^2) O(target)
        possible_min = sum(min(row) for row in mat) #O(RC)
        if possible_min > target: return possible_min - target
        
        nums = {0}
        for row in mat: # no need to go higher than 2*target - possible_min
            nums = {x + i for x in row for i in nums if x + i <= 2*target - possible_min}
        # target = 10, min_sum = 7  => the range: 7~13   2*target - possible_min = 13 
        return min(abs(target - x) for x in nums)
        """
        



        """
        #Brute force
        # O(R^4)
        nums = {0}
        for row in mat:
            nums = {num+val for val in row for num in nums}
        
        return min(abs(num-target) for num in nums)
        """
29600