0
$\begingroup$

Given a multiset of $2m$ positive numbers, $S=\{s_1,s_2,\ldots,s_{2m}\}$ and given $m$ targets $t_1,t_2,\ldots,t_m$. Can we partition $S$ into $m$ pairs $(a_i,b_i)$ such that $a_i+b_i=t_i$, where $a_i\ne b_i$ and $a_i,b_i\in S$?

For example for $S=\{1,4,6,1,2,5\}$ and $t_1=7$, $t_2=t_3=6$. The answer is YES and the pairs are $(1,6)$, $(2,4)$, and $(1,5)$.

Improve this question
$\endgroup$
3
  • $\begingroup$ What did you try? Where did you get stuck? Did you try to find an efficient algorithm? Did you try to prove it NP-complete? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W.♦ Nov 8 '19 at 23:50
  • 1
    $\begingroup$ The same reduction works. $\endgroup$ – xskxzr Nov 9 '19 at 3:20
  • $\begingroup$ @xskxzr Thank you. $\endgroup$ – Jika Nov 9 '19 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.