0

I have an array of 2n distinct non-negative integers, the goal is to find if it's possible to put all integers into pairs such that the sum of the absolute difference of all pairs is equal to a specific number x.
Example: [1, 2, 3, 5, 8, 10] If x=5, it is possible because the total absolute difference of (1, 2), (3, 5), and (8, 10) is 5.
If x=10 it is not possible.

att9899
  • 1
  • 2
    It seems like a hard question in general which may require brute force. You can at least note that if your array contains an odd number of odd integers then any sum of absolute differences of pairs must be odd and could not be even which would immediately rule out $x=10$ in this example. This is seen by a simple modular arithmetic argument. – JMoravitz Jul 27 '22 at 12:30
  • 2
    This looks similar to the N-Queens problem if you put the differences in a matrix, you can not traverse the same column and row you traversed in the past – Danny Blozrov Jul 27 '22 at 12:32
  • First instinct is that this should be NP-complete, with a reduction from the Subset Sum Problem https://en.wikipedia.org/wiki/Subset_sum_problem – JBL Jul 28 '22 at 12:41

0 Answers0