This is a variation of Subset Sum Problem with fixed subset size. (You are facing the optimization problem).
The existence solution (Is there a subset that sums exactly to pi
) is discussed thoroughly in the thread: Sum-subset with a fixed subset size.
In your problem (the optimization problem) - if you can repeat an element more than once - it is easily solveable in O(n2log) with O(n2) additional space as follows:
- Create an array of size O(n2) containing all possible sum of pairs. Let it be
arr
. - Sort arr -
O(n^2logn)
- For each element
e
ofarr
- binary search inarr
to find the element closest topi-e
. - Yield the two pairs that got the best result in step 3.
The complexity of step 3 is O(logn)
per iteration, and n2 iterations - so O(n^2logn)
total.