Minimize the Difference Between Target and Chosen Elements

LeetCode 1981, Minimize the Difference Between Target and Chosen Elements, asks you to pick exactly one element from each row of a matrix and minimize the absolute difference between the sum of chosen elements and a given target. You cannot skip a row, and you cannot pick more than one element from any row.

This is a classic "reachable sums" problem. Instead of tracking which specific elements you pick, you track the set of all sums you can build row by row. After processing every row, you scan the final set of sums and return the one closest to the target.

The approach: row-by-row DP with a set of reachable sums

Think of each row as a decision point. Before you process any row, you have a set of sums that are reachable so far. For the first row, the reachable set starts as {0} (you have not picked anything yet). When you process a row, you take every sum in the current set and add every value in that row to it. The result is a new set of reachable sums.

After processing all rows, you have every possible sum you could build by picking one element per row. The answer is just the minimum of |s - target| across all sums s in the final set.

Why does this work? Because you never need to know which elements produced a given sum. You only need to know that the sum is reachable. A set captures exactly that information, and deduplication keeps it from growing out of control when multiple paths lead to the same sum.

The code

def minimizeTheDifference(mat, target):
    possible = {0}
    for row in mat:
        next_possible = set()
        for s in possible:
            for val in row:
                next_possible.add(s + val)
        possible = next_possible
    return min(abs(s - target) for s in possible)

This is the clean version that captures the core idea. For large inputs, the set of reachable sums can grow very large, especially when values are small and the matrix is wide. A practical optimization is to prune sums that are far above the target. If a sum already exceeds the target by more than any possible reduction from future rows, you can drop it. A simple approach: keep only sums up to target + max_remaining, where max_remaining is the sum of the maximum elements in the remaining rows. Any sum above that threshold cannot possibly get closer to the target than a sum that is already closer.

def minimizeTheDifference(mat, target):
    possible = {0}
    row_maxes = [max(row) for row in mat]
    for i, row in enumerate(mat):
        next_possible = set()
        max_above = sum(row_maxes[i + 1:])
        cap = target + max_above
        for s in possible:
            for val in row:
                next_possible.add(s + val)
        # Keep all sums at or below cap, plus the smallest sum above cap
        below = {s for s in next_possible if s <= cap}
        above = [s for s in next_possible if s > cap]
        if above:
            below.add(min(above))
        possible = below
    return min(abs(s - target) for s in possible)

Visual walkthrough

Let's trace through the example with mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] and target = 13.

At each step, the set of reachable sums grows as you combine previous sums with the current row's values. By the end, the set contains every possible total. Since 13 is in the final set, the answer is 0.

Complexity analysis

Without pruning, S can be as large as m * max_val * n in the worst case, because each row can shift every existing sum by up to n different amounts. With pruning, S stays bounded by the range of useful sums near the target, which makes the solution practical for the given constraints.

Building blocks

This problem is built on the reachable sums DP pattern. You maintain a set of achievable values and expand it one decision at a time. The same structure appears in several related problems:

• State: a set of sums reachable after processing the first i rows
• Transition: for each sum s and each value v in row i, add s + v to the next set
• Answer: scan the final set and find the value closest to the target

This pattern is a close relative of subset sum and coin change. In Coin Change, you track reachable amounts using an array. In Partition Equal Subset Sum, you track reachable sums with a boolean DP. Here, you track reachable sums with a set. The core idea is identical: build up all possible values one step at a time, then query the result.

The row-by-row structure is also similar to Number of Dice Rolls With Target Sum. In that problem, each die is a "row" and each face value is a "column." The difference is that dice rolls count the number of ways to reach a target, while this problem only cares whether a sum is reachable.

Edge cases

• Single row: the answer is just min(|val - target|) for each value in that row.
• Target is achievable: if the target sum is in the reachable set, the answer is 0.
• All sums exceed target: this can happen when every element in every row is large. The closest sum is the minimum of the final set, and the answer is min_sum - target.
• All sums fall below target: when every element is small and the matrix has few rows. The closest sum is the maximum of the final set, and the answer is target - max_sum.
• Duplicate values in a row: these do not affect correctness because the set deduplicates automatically, but they do waste time in the inner loop. You can deduplicate each row before processing to avoid redundant work.
• Large matrix with small values: the set of reachable sums can grow very large. Use the pruning optimization described above.

From understanding to recall

The reachable sums approach is one you will see again and again in DP problems that involve choosing from multiple groups. The core loop (iterate over previous sums, add each option, collect into a new set) is almost identical in every variation. What changes is the final query: sometimes you want the closest value to a target, sometimes you want a boolean "is the target reachable," sometimes you want a count.

Reading through this explanation, the idea probably feels natural. But reproducing it under time pressure is a different skill. You need to remember to start with {0}, to replace the set at each row (not accumulate across rows), and to handle the pruning step if the input is large. These details slip away if you only read about them once.

Spaced repetition locks them in. You write the solution from scratch at increasing intervals, and after a few reps, the set-based DP loop becomes automatic. The reachable sums pattern is one of roughly 60 building blocks in the CodeBricks system. Drilling it individually is faster than grinding random problems and hoping the pattern sticks.

Related posts

• Coin Change - The classic DP problem for tracking reachable amounts, using an array instead of a set
• Partition Equal Subset Sum - Another reachable sums problem where you check if a specific target is achievable
• Target Sum - Counting the number of ways to reach a target by assigning + or - to each element, using the same set expansion idea