Number Partitioning with Cardinality Constraint: Is that NP-Hard? Given a set of integers $S=\{a_1, \dots, a_n\}$ where $a_i > 0$ and $n$ is an even number, we want to find $A \subset S$ so that:
$$
\left| \sum_{a \in A}a - \sum_{b \in S-A}b \right|
$$
is minimized. This problem is very well known to be NP-hard. If we add a constraint $|A| = |S-A|$, is the problem is still NP-hard?
 A: Yes, because you can multiply all of the existing numbers in $S$ by $2|S|^2$ and extend $S$ with the numbers $1$ through $|S|$. A minimal solution to the extended problem with the $2|A|=|S|$ constraint will then also be a solution to the original problem without such constraint, just by ignoring what happened to the new integers in it.
If someone gives me a polynomial solver for the constrained problem, I can use this reduction to solve the original problem in polynomial time. Thus, since the original problem is known to be NP-hard, the constrained one is NP-hard too.
For example, $\{100,200,300\}$ without constraint reduces to $\{1,2,3,1800,3600,5400\}$ with constraint. The optimal solution to the latter problem is $\{3,1800,3600\},\{1,2,5400\}$, with a difference of $|5403-5403|=0$. Because this difference is strictly less than $3^2$, the original unconstrained $\{100,200,300\}$ has a solution with difference strictly less than 1.
A: Garey and Johnson, Computers and Intractability, page 223: 
"A3.2 Weighted set problems 
"[SP12] Partition 
"Instance: Finite set $A$ and a size $s(a)$ in ${\bf Z}^+$ for each $a$ in $A$. 
"Question: Is there a subset $A'\subseteq A$ such that $\sum_{a\in A'}s(a)=\sum_{a\in A-A'}s(a)$? 
"Reference: [Karp, 1972]. Transformation from 3-dimensional matching (see Section 3.1.5). 
"Comment: Remains NP-complete even if we require that $|A'|=|A|/2$ ...." 
I'm aware that this is about equality while the original is about minimization. Still, might not be a bad idea to see what's in the book. 
