# Minimize the Difference Between Target and Chosen Elements
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimize-the-difference-between-target-and-chosen-elements)
Canonical: https://scaleengineer.com/dsa/problems/minimize-the-difference-between-target-and-chosen-elements
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
**Companies:** [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimize-the-difference-between-target-and-chosen-elements/image0.png) 

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

![](https://assets.glich.co/dsa/minimize-the-difference-between-target-and-chosen-elements/image1.png) 

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

![](https://assets.glich.co/dsa/minimize-the-difference-between-target-and-chosen-elements/image2.png) 

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

# Approaches
## Brute-Force Recursion (Backtracking)
This approach explores every possible combination of chosen elements, one from each row, to find the sum that is closest to the target. It uses a recursive backtracking method to generate all combinations.
**Time:** O(n^m)

For each of the `m` rows, we have `n` choices. This leads to a total of `n * n * ... * n` (`m` times) or `n^m` possible combinations to check. Given the constraints (`m, n <= 70`), this is computationally infeasible. · **Space:** O(m)

The space complexity is determined by the maximum depth of the recursion stack, which is equal to the number of rows, `m`.
**Pros:** Simple to understand and implement.; Conceptually straightforward.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
We define a recursive function, say `backtrack(row, currentSum)`, where `row` is the current row index we are considering and `currentSum` is the sum of elements chosen from previous rows. The function works as follows:

When we are at a certain `row`, we iterate through all its elements. For each element, we add it to the `currentSum` and recursively call the function for the next row (`row + 1`).

The recursion stops when we have processed all the rows (i.e., `row == m`). At this base case, we have a complete sum from one element per row. We then compute the absolute difference between this sum and the `target` and update our global minimum difference if the current one is smaller.

This method exhaustively checks every single one of the `n^m` possible combinations.
### Algorithm
- Initialize a global variable `minDifference` to a very large value.
- Define a recursive function `backtrack(row, currentSum)`.
- The base case for the recursion is when `row` equals the total number of rows `m`. At this point, a full combination has been chosen. Calculate the absolute difference `abs(currentSum - target)` and update `minDifference` if this new difference is smaller.
- In the recursive step, for the current `row`, iterate through each element `mat[row][j]` from `j = 0` to `n-1`.
- For each element, make a recursive call `backtrack(row + 1, currentSum + mat[row][j])` to explore the next level of choices.
- The initial call to start the process is `backtrack(0, 0)`.
- After the initial call returns, `minDifference` will hold the minimum possible absolute difference.

## Bottom-Up Dynamic Programming
This approach uses dynamic programming to systematically build the set of all possible sums that can be achieved. Instead of recomputing sums in a recursive manner, it builds upon the sums from the previous row to find the sums for the current row.
**Time:** O(m * n * MAX_SUM)

Where `MAX_SUM` is the maximum possible sum, approximately `m * 70`. For each of the `m` rows, we iterate through the current set of possible sums (size up to `MAX_SUM`) and for each sum, we iterate through the `n` elements of the row. With the given constraints, this is roughly `70 * 70 * (70*70)`, which is around `2.4 * 10^7` operations, which might be acceptable. · **Space:** O(m * 70)

We need to store the set of possible sums. The maximum value of a sum is `m * 70`. In the worst case, we might need to store a number of distinct sums proportional to this maximum value. Two sets are used, so the space is `O(MAX_SUM)`.
**Pros:** Much more efficient than the brute-force approach.; Guaranteed to find the optimal solution by exploring all reachable states (sums).
**Cons:** The time and space complexity depend on the maximum possible sum, which can be large (`m * 70`).; It may be too slow if the constraints on `m` and matrix values were slightly larger, as it computes all possible sums without any pruning.
### Explanation
We can determine all possible sums achievable row by row. Let `sums` be a set representing all possible sums using elements from the first `i` rows. To find the possible sums for the first `i+1` rows, we take each sum `s` in `sums` and add each element `x` from row `i+1` to it, creating a new set `next_sums`.

We start with a set containing just `0` (representing the sum before choosing any elements). We then iterate through each row of the matrix. For each row, we generate a new set of sums by adding each element of the row to every sum calculated from the previous rows. This process continues until all rows are processed.

Finally, we iterate through the set of all possible final sums and find which one has the minimum absolute difference from the `target`.
### Algorithm
- Initialize a `Set<Integer>` called `possibleSums` and add `0` to it. This set will store all achievable sums at each stage.
- Iterate through each `row` of the matrix `mat` from top to bottom.
- In each iteration, create a new empty `Set<Integer>` called `nextPossibleSums`.
- For each `sum` currently in `possibleSums`, and for each `element` in the current `row`, add their sum (`sum + element`) to `nextPossibleSums`.
- After iterating through all elements of the current row, replace `possibleSums` with `nextPossibleSums`.
- After processing all the rows, `possibleSums` will contain all possible final sums.
- Initialize `minDifference` to a very large value.
- Iterate through each `finalSum` in the final `possibleSums` set and update `minDifference` with `min(minDifference, abs(finalSum - target))`.
- Return `minDifference`.

## Optimized Bottom-Up DP with Pruning
This is a highly optimized version of the bottom-up DP approach. It leverages a key observation to prune the search space of possible sums at each step, which dramatically improves performance, especially given the problem's constraints.
**Time:** O(m * n * target)

For each of the `m` rows, we iterate through the current set of sums. Due to pruning, the size of this set is bounded by `O(target)`. For each of these sums, we iterate through the `n` elements of the row. This results in a much faster runtime compared to the unoptimized DP. · **Space:** O(target)

The size of the set `sums` is bounded at each step. It contains sums `<= target` (at most `target + 1` of them) and at most one sum `> target`. Thus, the space required is proportional to `target`.
**Pros:** Very efficient, with time and space complexity dependent on `target` instead of the maximum possible sum.; Passes well within the time limits for the given constraints.
**Cons:** The logic is slightly more complex to reason about compared to the standard DP approach.
### Explanation
The core idea is that if we have multiple partial sums that are already greater than the `target`, we only need to care about the smallest one. Any path continuing from a larger partial sum will always result in a final sum that is further from the `target` than the one from the smallest partial sum (since all matrix elements are positive).

So, at each step of building our sums row by row, we maintain a set of all achievable sums that are less than or equal to `target`, and only the single smallest sum that is greater than `target`. This keeps the size of our set of sums bounded by `target + 2`.

This pruning transforms the complexity from being dependent on the potentially large `MAX_SUM` to being dependent on the much smaller `target` value.
### Algorithm
- Initialize a `Set<Integer>` called `sums` and add `0` to it.
- Iterate through each `row` in the matrix `mat`.
- For each row, create a temporary set `nextSumsLeTarget` to store new sums less than or equal to `target`, and an integer `minNextSumAboveTarget` initialized to infinity to track the smallest new sum greater than `target`.
- Iterate through each existing partial `s` in `sums` and each `element` `x` in the current `row`:
  - Calculate `newSum = s + x`.
  - If `newSum <= target`, add it to `nextSumsLeTarget`.
  - If `newSum > target`, update `minNextSumAboveTarget = min(minNextSumAboveTarget, newSum)`.
- After processing the row, update `sums` to be `nextSumsLeTarget`.
- If `minNextSumAboveTarget` was updated (i.e., is not infinity), add this single value to `sums`.
- After iterating through all rows, `sums` contains a pruned set of final, relevant sums.
- Calculate the minimum difference by iterating through the final `sums` set and comparing `abs(s - target)` for each sum `s`.

# Solutions
### Java

```java
class Solution {
public
  int minimizeTheDifference(int[][] mat, int target) {
    Set<Integer> f = new HashSet<>();
    f.add(0);
    for (var row : mat) {
      Set<Integer> g = new HashSet<>();
      for (int a : f) {
        for (int b : row) {
          g.add(a + b);
        }
      }
      f = g;
    }
    int ans = 1 << 30;
    for (int v : f) {
      ans = Math.min(ans, Math.abs(v - target));
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimizeTheDifference(vector<vector<int>> &mat, int target) {
    vector<int> f = {1};
    for (auto &row : mat) {
      int mx = *max_element(row.begin(), row.end());
      vector<int> g(f.size() + mx);
      for (int x : row) {
        for (int j = x; j < f.size() + x; ++j) {
          g[j] |= f[j - x];
        }
      }
      f = move(g);
    }
    int ans = 1 << 30;
    for (int j = 0; j < f.size(); ++j) {
      if (f[j]) {
        ans = min(ans, abs(j - target));
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int: f = {0} for row in mat: f = set(a + b for a in f for b in row) return min(abs(v - target) for v in f)

```