<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 __init__(self):
        self.memo = {}

    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:

        # s = set([0])

        # for row in mat:
        #     row_set = set(row)
        #     temp_set = set()
        #     for e1 in s:
        #         for e2 in row_set:
        #             temp_set.add(e1 + e2)
        #     s = temp_set
        
        # return min([abs(e - target) for e in s])
        # return 0

        #One row at a time, 
        #Iterate through all elements in a row
        #Add element, recurse
        #Backtrack
        #Return minimum

        #O(cols ^ rows) - brute force
        def backtrack(row, runningSum):
            key = (row, runningSum)
            if key in self.memo:
                return self.memo[key]

            if row >= len(mat):
                return abs(target-runningSum)
            
            minimum = float("+inf")
            #Instead, todo:
            #Sort the row, smallest items - sum below target, middle items - sum close to target, largest items - sum above target
            last = None
            lastExplored = None
            #KEY TAKEAWAYS:
            #Run only for unique elements from the row
            #(Unique) elements in ascending order,

            for number in sorted(set(mat[row])):
                # if last == None or number != last:
                    # last = number
                    # runningSum += number
                explored = backtrack(row + 1, runningSum + number)
                if lastExplored is not None and explored > lastExplored:
                    break
                lastExplored = explored
                # print(explored)
                minimum = min(explored, minimum)
                    # runningSum -= number
            # print()
            
            self.memo[key] = minimum
            return self.memo[key]
            # return minimum
        
        return backtrack(0, 0)
        
4423