# Partition a multiset into pairs that sum up to given numbers?

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)$$.

• 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. – D.W. Nov 8 '19 at 23:50
• The same reduction works. – xskxzr Nov 9 '19 at 3:20
• @xskxzr Thank you. – Jika Nov 9 '19 at 3:25