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 ?


1 Answer 1


I'm unable to add comments but I think this problem can be simplified to:

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.

  • 1
    $\begingroup$ And this in turn is almost the subset sum problem. $\endgroup$ Commented Aug 3, 2017 at 18:26
  • $\begingroup$ Can you explain how to reduce to subset sum problem ? $\endgroup$
    – Noctisdark
    Commented Aug 3, 2017 at 18:35
  • $\begingroup$ @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?". $\endgroup$ Commented Aug 3, 2017 at 21:21
  • $\begingroup$ I actually thought about it and said it would likely timeout, thanks for the answer, really :). $\endgroup$
    – Noctisdark
    Commented Aug 4, 2017 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.