$\underline{\mathsf{EQUAL\mbox{ }k-COMPLEMENTARY\mbox{ }SUBSET\mbox{ }SUM(EkCSS)} }$Problem:Input: $a_1,\dots,a_n,b\in \mathbb Z$, with distinct $a_i$ and $k\in\Bbb Z^+$.Output: $k$ $\mbox{ }\underline{not\mbox{ }necessarily\mbox{ }disjoint}$ subsets of $a_i$s of sizes $n_1,\dots,n_k$ satisfying $\sum_{i=1}^kn_i=n$ such that each subset sums to $b$. (1) Is $\mathsf{EkCSS}$ $NP$-complete?(2) If we replace requiring $k$ subsets by requiring $\lceil\log^cn\rceil$ subsets for some fixed $c\in\Bbb R^+$ does the problem remain NP complete?(3) Is $\mathsf{EkCSS-Diff}\mbox{ }$ $NP$-complete where $\mathsf{EkCSS-Diff}$ is same as $\mathsf{EkCSS}$ but with added condition $n_i\neq n_j\forall i\neq j$ (different subset sizes)?
Multiple subset sum where subsets have complementary cardinality
np complete;subset sum
This is a reduction (attempt :-) from this slight variant of SUBSET SUM (which should be NPC) to prove that E2CSS is NP-complete:Given integers $A = a_1,a_2,...,a_n\;; a_i > 0$ (with the additional constraint that n is even) and a target sum $b$. Does exist $X \subseteq A$ such that $|X|=2m, m \geq 1$ (i.e. $|X|$ is even and greater than or equal to 2) and $sum(X)=b$?  Reduction: suppose that $2^k > b+\sum_{i=1}^n |a_i|$; then we expand $A$ adding a dummy solution$A' = A \cup \{ -2^k, 2^k + b\}$If $X$ is a solution for the original problem, then  $X, Y= \{ -2^k, 2^k + b\}$ are two distinct solutions for $A'$ and target sum $b$. Now we can further expand $A'$ to $|A''|$ adding padding pairs of integers that do not affect the sums but can be used to pad $X$ and $Y$ up to $|X|+|Y|=|A''|$. We have$|A'|=n+2$, so we add $n/2-1$ pairs $\{2^{k+i},-2^{k+i}\}$, $i=1..n/2-1$:$A'' = \{a_1,...,a_n,-2^k, 2^k + b, 2^{k+1},-2^{k+1},...,2^{k+n/2-1},-2^{k+n/2-1}\}$, $|A''|=2n$Using all the $n/2-1$ padding pairs we can build a set $Z$ such that $sum(Z)=0$ and $|Z|=2(n/2-1)=n-2$.We can notice that using the dummy solution and the padding pairs we can build a set $Y'=Y \cup Z$, $sum(Y')=b$, $|Y'|=n$ (which is half the size of $A''$). So in order to get another different solution we  must use two or more of the $a_i$ plus some padding pairs.In the figure a binary expansion of the elements of $A''$:The above reduction works for any fixed $k$: just start with the (NP-complete) subset sum variant in which $k$ divides $n$ and $|X|\geq k$, then add $k-1$ dummy solutions (each dummy solution made with $k$ elements) and $(n/k-1)$ padding k-tuples.If $k$ is part of the input (EkCSS), we have a simple generalization of the E2CSS problem and its NP-hardness follows immediately by the NP-completeness of E2CSS; the reduction is trivial: given an instance $A'',b$ of the E2CSS problem, just transform it to $A'',b,k=2$ which is a valid instance of the EkCSS problem. So EkCSS is NP-complete.(Very informally) The EkCSS-diff should be NP-complete, too and the reduction from EkCSS is: attach to every $a_i$ a group of elements $T_i$ of size $m_i=(i+1)*n$:$T_i= \{ a_i+1*2^u, 2*2^u,3*2^u,....,(m_i-1) 2^u,-2^u*\sum_{j=1}^{m_i-1} \}, |T_i|=(i+1)*n$The first element of $T_i$ which replaces $a_i$, contains two detached bit components the original $a_i$ and $1*2^u$; but the only way to clear $1*2^u$ is to include the other elements of $T_i$ and the final one that is the only negative element (it clears all the previous $2^u$ components).Every $T_i$ have distinct values for $u$ (and choosen in such a way that the sums don't interfere with each other and with the sum of the original $a_i$s).