# Minimum difference of sums

So hey, I've recently found this problem online and I tried hard to solve but couldn't found an efficient solution. The problem statement is:

Given and two integers $n$ and $k$ and an array $A$ containing $n$ pairs of integers of the form $(a, b)$ and $d$ defined as $d = |\sum_{x \in E} x[1] -x[0]|$ where is $E$ is a subset of $A$ containing exactly $k$ elements. Find the minimum value of $d$.

To illustrate the problem, consider $n = 3$, $k = 2$, $A = [(2, 1), (0, 2), (1, 2)]$.

The minimum value of $d$ is $0$. We can pick $E = [(1, 2), (2, 1)]$ containing $k = 2$ values of $A$ then $d = |(1 - 2) + (2 - 1)| = |0| = 0$.

I tried to solve this problem but only came up with the brute force solution which is terrible in terms of time complexity.

How can one solve this problem efficiently ?

B = []
for pair in A:
B.append(pair[0] - pair[1])

min_sum(B, k)


min_sum returns k elements that add up to give the smallest number possible (absolute value). This (at least to me) feels easier to work with.

• And this in turn is almost the subset sum problem. – Gribouillis Aug 3 '17 at 18:26
• Can you explain how to reduce to subset sum problem ? – Noctisdark Aug 3 '17 at 18:35
• @Noctisark Using Izaan's notation, the subset sum problem can be formulated as "Is any of min_sum(B, 1), ...,min_sum(B, N) equal to zero?". – Gribouillis Aug 3 '17 at 21:21
• I actually thought about it and said it would likely timeout, thanks for the answer, really :). – Noctisdark Aug 4 '17 at 5:26