Introduction

The Codility MinAbsSum problem asks for the smallest possible absolute sum you can obtain by assigning either a plus or minus sign to each element of an array. The key insight is that after taking absolute values, the problem becomes a subset-sum style partition problem: split the values into two groups whose sums are as close as possible.

A direct brute-force search over all sign combinations is exponential, so the practical solution uses dynamic programming.

Reduce The Problem To Partitioning

Suppose the array is A. If you replace every value by its absolute value, the sign-choice problem becomes:

• choose some values to contribute positively
• choose the remaining values to contribute negatively
• make the two group sums as close as possible

If the total sum of absolute values is S, then the ideal target is to find a subset whose sum is as close as possible to S / 2. Once you find that, the final answer is:

abs(S - 2 * subset_sum)

That is the same partitioning idea that appears in several classic DP problems.

A Simple Dynamic Programming Version

For smaller sums, a boolean subset-sum DP is easy to understand:

1def min_abs_sum(arr):
2    values = [abs(x) for x in arr]
3    total = sum(values)
4    target = total // 2
5
6    possible = [False] * (target + 1)
7    possible[0] = True
8
9    for value in values:
10        for s in range(target, value - 1, -1):
11            if possible[s - value]:
12                possible[s] = True
13
14    best = max(s for s, ok in enumerate(possible) if ok)
15    return total - 2 * best
16
17
18print(min_abs_sum([1, 5, 2, -2]))

This works by tracking which subset sums up to target are reachable.

Why Codility Usually Needs Counting Optimization

The real Codility version is designed so that the raw sum can be large, which makes a naive DP over every element less efficient. A common optimization is to count how many times each absolute value appears and then process those counts instead of treating every duplicate separately.

That improves performance because many arrays contain repeated values, and the DP can reuse frequency information rather than recomputing equivalent transitions for each copy.

Even if you do not implement the count-optimized version in an interview explanation, understanding the subset-sum reduction is the main conceptual step.

Interpreting The Result

If the DP says a subset sum of best is reachable, then the opposite side has sum total - best. The absolute difference between the two sides is:

total - 2 * best

That value is the minimum absolute sum achievable by assigning signs.

So the DP is not directly choosing plus or minus signs. It is searching for the best partition of the absolute values.

Common Pitfalls

The biggest mistake is trying to brute-force sign assignments directly. That leads to O(2^N) thinking and does not scale.

Another pitfall is forgetting to convert values to absolute values first. The optimization logic depends on partitioning magnitudes, not preserving the original signs.

A third issue is misunderstanding the final formula. The goal is not to maximize the subset sum, but to maximize it only up to half of the total so that the two sides stay as balanced as possible.

Summary

• MinAbsSum is a partition problem disguised as a sign-assignment problem.
• Convert the values to absolute values first.
• Use subset-sum style dynamic programming to get as close as possible to half the total sum.
• The final answer is total - 2 * best_subset_sum.
• Efficient solutions often optimize further by counting repeated absolute values.