Sets of Complementary Sums

Let $Q$ be a valid set and let $M=\max Q.$ The largest complementary sum corresponds to the smallest distinct array value. That one observation is the door; the rest is just counting.

A cleaner condition

Suppose the original array has total sum $s$. For every $q\in Q$, the corresponding distinct array value is $s-q.$ Let the smallest distinct array value be $y$. Since $M$ is the largest complementary sum, $s=M+y.$

Now define $b=M+1-q.$ Because $M\in Q$, the value $b=1$ is always present. Also the $b$ values are distinct positive integers.

The corresponding array value is $s-q=(M+y)-q=(M+1-q)+(y-1)=b+y-1.$ Every distinct array value must appear at least once, so the sum of the distinct required values cannot exceed the total sum: $\sum_{q\in Q}(b+y-1)\le M+y.$ There are $n$ elements, so $\sum b+n(y-1)\le M+y,$ which becomes $\sum b+(n-1)(y-1)\le M+1.$ Since $y\ge 1$, we get the necessary condition $\boxed{\sum b\le M+1}.$ In terms of $Q$, this is $\boxed{\sum_{q\in Q}(M+1-q)\le M+1}.$

Now prove it is sufficient too. If we have distinct positive integers $B$ with $1\in B$ and $\sum_{b\in B}b\le M+1,$ choose total sum $s=M+1.$ Use each value $b\in B$ once. If the sum is short by $R=M+1-\sum B$, add $R$ extra copies of value $1$. This creates no new complementary sum because $1$ was already present. The produced set is exactly $Q=\{M+1-b\mid b\in B\}.$ So the original definition is equivalent to counting pairs $(M,B)$ where:

• $1\le M\le x$;
• $B$ has $n$ distinct positive integers;
• $1\in B$;
• $\sum B\le M+1$.

No overcounting happens because $M=\max Q$ is uniquely determined by $Q$.

Counting the pairs

Sort $B=\{b_1<b_2<\cdots<b_n\}.$ Since $1\in B$, we have $b_1=1$. The smallest possible set is $\{1,2,\ldots,n\},$ with sum $S_0=\frac{n(n+1)}2.$ For this minimum set, the smallest possible maximum is $M_0=S_0-1.$ If $M_0>x$, then even the cheapest possible set is too expensive, so the answer is $0$.

Otherwise write $b_i=i+e_i.$ Because the $b_i$ are strictly increasing, $0=e_1\le e_2\le\cdots\le e_n.$ Let $E=\sum_{i=1}^n e_i.$ Then $\sum B=S_0+E.$ For this $B$, valid maxima satisfy $M\ge \sum B-1=M_0+E.$ If $M$ is larger, call the extra slack $r=M-(M_0+E)\ge 0.$ So every valid pair corresponds to total increase $D=E+r,$ with $D\le x-M_0.$

Now convert the nondecreasing sequence into independent variables: $g_2=e_2,$ $g_3=e_3-e_2,$ $\ldots,$ $g_n=e_n-e_{n-1}.$ All $g_i\ge 0$. Their contribution to $E$ is $E=(n-1)g_2+(n-2)g_3+\cdots+1\cdot g_n.$ The slack $r$ is another free variable of weight $1$.

So the generating function for $D$ is $\frac{1}{(1-z)^2(1-z^2)(1-z^3)\cdots(1-z^{n-1})}.$ The two weight-$1$ factors are $g_n$ and the slack $r$. Easy detail to miss, and yes, that is exactly the kind of tiny thing that nukes a solution.

Let $dp[d]$ be the coefficient of $z^d$. The answer is $\sum_{d=0}^{x-M_0}dp[d].$

DP

This is standard unbounded knapsack:

• add weight $1$ twice;
• add each weight $2,3,\ldots,n-1$ once.

For each weight $w$: $dp[s]\mathrel{+}=dp[s-w].$

For $n=1$, every singleton set works, so the answer is simply $x$.

The DP only needs degrees up to $L=x-\left(\frac{n(n+1)}2-1\right),$ so the runtime is easily within limits.