Number Partitioning with Cardinality Constraint: Is that NP-Hard?

Question

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?

Answer 1

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.

Answer 2

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.