Number Partition

Consider a slightly generalized problem: divide the numbers in $[1,m]$ into three piles with sums $s_1,s_2,s_3$, where some $s_i$ may be $0$.

For $m \geq 3$, the only impossible cases are the following:

• At least two of the $s_i$ are equal to $1$.
• At least two of the $s_i$ are equal to $2$.

A pile with sum $1$ must be exactly $\{1\}$, and a pile with sum $2$ must be exactly $\{2\}$, so the cases above are impossible.

We construct the partition by placing the numbers from large to small. Suppose we are currently processing $m,m-1,\cdots,1$. If the remaining target sums are $s_1,s_2,s_3$, placing into pile changes the remaining sum of that pile to . Try all piles where this is nonnegative, and choose one that keeps the remaining instance on feasible by the condition above.

Starting from a feasible state, such a choice always exists. Therefore, repeating this for $m=n,n-1,\cdots,1$ gives a valid partition.

If the initial state is impossible, print $\text{NO}$. Otherwise, output the three piles obtained by the construction.

Solution written by GPT5.5