Introduction

Minimizing the difference between the averages of two subsets is not exactly the same as the classic equal-sum partition problem. The subset sizes matter too. A correct solution needs to consider both the number of chosen elements and their sum.

Write the objective carefully

Suppose the full set has total sum T and size n. If one subset has size k and sum s, then the other subset has size n-k and sum T-s.

The average difference is:

$\left|\frac{s}{k} - \frac{T-s}{n-k}\right|$

After algebra, this is equivalent to minimizing:

$|n \cdot s - k \cdot T|$

for some valid subset size k, while also accounting for the denominator k(n-k) in the original expression.

That is why simply minimizing the raw difference of subset sums is not always enough.

A dynamic programming strategy

A useful exact approach is dynamic programming over:

• how many elements were chosen
• what sum they produce

For each possible subset size k, you track which sums are achievable. Then you evaluate which reachable sum gives the smallest average difference.

A compact Python version for positive integers looks like this:

1def min_average_difference_partition(nums):
2    n = len(nums)
3    total = sum(nums)
4
5    dp = [set() for _ in range(n + 1)]
6    dp[0].add(0)
7
8    for num in nums:
9        for k in range(n - 1, -1, -1):
10            for s in list(dp[k]):
11                dp[k + 1].add(s + num)
12
13    best = None
14
15    for k in range(1, n):
16        for s in dp[k]:
17            diff = abs(s / k - (total - s) / (n - k))
18            if best is None or diff < best[0]:
19                best = (diff, k, s)
20
21    return best
22
23
24print(min_average_difference_partition([1, 2, 7, 10]))

This gives you the best average difference along with the chosen subset size and sum.

Why subset size matters

Imagine two candidate subsets with similar sums but very different sizes. Their averages can be quite different. That is the key reason the problem is more subtle than ordinary equal-sum partitioning.

For example, compare:

• subset A with sum 10 and size 2, average 5
• subset B with sum 10 and size 5, average 2

Same sum, very different average. So the algorithm cannot ignore how many elements each subset contains.

Recovering the actual subsets

The DP above finds the best objective value, but not the exact chosen elements. To reconstruct the subsets, store predecessor information while filling the DP table, or backtrack from the winning (k, s) state.

That adds implementation detail, but the principle stays the same: track which choices created each reachable state.

If you only need the minimum difference value, the simpler state-tracking version is enough.

Complexity and practical limits

The DP approach is exact, but it depends on the sum range. If the numbers are large, the number of reachable sums can become expensive.

That makes the approach practical mainly when:

• the set is not too large
• the values are moderate enough for sum-based DP

For larger inputs, you may need heuristics, approximation, or problem-specific constraints.

Common Pitfalls

The biggest pitfall is reducing the problem to ordinary equal-sum partitioning. Equal sums do not guarantee equal averages unless the subset sizes are also controlled.

Another issue is forgetting that empty subsets are invalid for average computation. Both subsets must contain at least one element.

It is also easy to implement a DP that tracks only sums and not subset sizes. That loses crucial information and can produce the wrong answer.

Finally, for large value ranges, the exact DP may become too expensive. In those cases, a heuristic may be more realistic, but it should be labeled as approximate rather than exact.

Summary

• Minimizing average difference is not the same as minimizing sum difference alone.
• A correct exact method tracks both subset size and achievable sums.
• Dynamic programming works well for moderate input sizes and value ranges.
• Reconstructing the actual subsets requires storing predecessor information.
• If the input is large, consider whether an approximate strategy is acceptable.