In the Balanced Partition problem, there are $2m$ nonnegative integers with sum $2s$. The goal is to decide whether they can be partitioned into two subsets of $m$ integers and sum $s$.
The problem is obviously in NP. I am trying to prove that it is NP-complete.
So far, I have found the following reduction from the standard Partition problem (which is the same problem but without the restriction on the number of integers). Given an instance $I$ of Partition with some $n$ integers, do for $k$ in $0,1,\ldots,n-1$:
Add $k$ zeros to $I$ ;
If $n+k$ is even, then try to find a balanced partition.
- If a balanced partition is found, remove the zeros and return it.
If no partition is found for any $k$, return "No partition".
The algorithm is correct since, if a solution to the original instance $I$ exists, then we can add some $k$ zeros to one of the parts to get a balanced partition, so for this $k$, a balanced partition will be found.
This shows that Balanced Partition cannot be solved in polynomial-time unless P=NP. However, it does not show that the problem is NP-complete; according to this Wikipedia page, "a problem is NP-complete if it belongs to NP and all problems in NP have polynomial-time many-one reductions to it", while the reduction I just described is not a many-one reduction - it is a Cook reduction.
Question: How can I prove that Balanced-Partition is NP-complete under a many-one reduction?