<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>

# 1981. Minimize the Difference Between Target and Chosen Elements

# You are given an m x n integer matrix mat and an integer target.

# Choose one integer from each row in the matrix such that the absolute difference between target and
# the sum of the chosen elements is minimized.

# Return the minimum absolute difference.

# The absolute difference between two numbers a and b is the absolute value of a - b.

# Example 1:
# Input: mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13
# Output: 0
# Explanation: 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.

# Example 2:
# Input: mat = [[1],[2],[3]], target = 100
# Output: 94
# Explanation: 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.

# Example 3:
# Input: mat = [[1,2,9,8,7]], target = 6
# Output: 1
# Explanation: The best choice is to choose 7 from the first row.
# The absolute difference is 1.

# Constraints:
# m == mat.length
# n == mat[i].length
# 1 <= m, n <= 70
# 1 <= mat[i][j] <= 70
# 1 <= target <= 800


class Solution:
    # Took me 2 attempts, 2 failures which each cost me more than 50mins trying
    # then I read the hints and got an idea for the DP using brute-force approach
    # basically we keep all the sums in a hashset and reuse them
    # and at the end we take the sums hashset and see which one is closest to the target

    # brute-force: find all possible sums
    # DP: keep all possible sums in a hash-set and reuse them for each row
    # you will have at most len(mat[i]) memory consumed!

    # runtime: O(n*m*2^n), space: O(2^n)
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        sums = {0}
        for i in range(len(mat)):  # O(n)
            current_sums = set()
            previous_sums = list(sums)  # O(m)
            for j in range(len(mat[i])):  # O(m)
                for possible_sum in previous_sums:  # O(2^n)??? why?
                    current_sums.add(possible_sum + mat[i][j])
            sums = current_sums

        best = math.inf
        for r in list(sums):
            best = min(best, abs(target - r))
        return best


# goal: MIN function
# we want to minimize the absolute difference of a sum of k numbers is minimized

# we can try all the possible combinations and at the end of the combination we compare it with
# target and take the minimum
# so 1, 4, 7, then 1, 4, 8, then 1, 4 , 9

# this will make runtime m^n, which when we put in memoization becomes m*n
# the problem with this is that we will have to update the target because the target varies
# after every choice we make

# if we chose 1 the target is not 13 anymore, it's 12

# if we find all the possible sums, we just need to find which one is the closest to 13 no?

# make a DFS function that calculates all the possible sums for each pair of i,j
# iterate through the first row and find the one with the closest to target!

# but what the memo[(i,j)] will store? an array of values?
# an array of values that add mat[i][j] with all the possible values of the next row

# we will have a single dp line which will hold a matrix!
# and for every row, we iterate through mat[row][column] and take the value and sum it with dp values?
# dp is initialized with values == 0, then we start from the last row doing bottom-up

# none of the above produced a correct answer, I had to read the tips

5795