<h2>The largest number is the soft number</h2>

<p>I claim that for any instance of your problem, if the instance is solvable (it is possible to partition the numbers using one soft number) then it is possible to solve the instance using the largest number as the sole soft number. This is easy to prove: any solution can be modified into a solution with the largest number as the soft number; simply place the number that is currently the soft number into the partition that contains the largest number and split the largest number among the parts of the partition instead.</p>

<h2>Packing problem</h2>

<p>Here is a problem that I will call the packing problem:</p>

<p>The input consists of a list of positive numbers <span class="math-container">$a_1, a_2, \ldots, a_k$</span> and one final number <span class="math-container">$\ell$</span> such that <span class="math-container">$\ell \ge a_i$</span> for all <span class="math-container">$i$</span>. Define <span class="math-container">$s = \frac{1}{3}\left(\ell + \sum_{i = 1}^ka_i\right)$</span>. Then the problem is to partition the list of <span class="math-container">$a_i$</span>s into three parts such that each part has sum at most <span class="math-container">$s$</span>.</p>

<p>I claim that the packing problem with inputs <span class="math-container">$a_1, \ldots, a_k$</span> and <span class="math-container">$\ell$</span> is equivalent to your problem with input list <span class="math-container">$a_1, \ldots, a_k, \ell$</span>. If it's possible to pack the numbers <span class="math-container">$a_1, \ldots, a_k$</span> into three groups each of sum at most <span class="math-container">$s$</span> then you can use <span class="math-container">$\ell$</span> as a soft number to round out each of the sums to exactly <span class="math-container">$s$</span>; thus you have a partition of <span class="math-container">$a_1, \ldots, a_k, \ell$</span> into three groups of sum <span class="math-container">$s$</span> using one soft number. If on the other hand <span class="math-container">$a_1, \ldots, a_k, \ell$</span> can be partitioned into three groups of sum <span class="math-container">$s$</span> using one soft number then the list can be partitioned into three groups of sum <span class="math-container">$s$</span> using <span class="math-container">$\ell$</span> as the soft number (by the result from the previous section). In this case the grouping of the <span class="math-container">$a_i$</span>s into three parts satisfies the condition that each part has sum at most <span class="math-container">$s$</span>.</p>

<h2>The packing problem with no small numbers</h2>

<p>Say that an instance of the packing problem "has no small numbers" if for every <span class="math-container">$i$</span>, <span class="math-container">$a_i &gt; \frac{\ell}{2}$</span>. I claim that you can reduce the packing problem to the packing problem with no small numbers.</p>

<p>Suppose that in packing problem instance <span class="math-container">$(a_1, \ldots, a_k), \ell$</span> some <span class="math-container">$a_i$</span> has <span class="math-container">$a_i \le \frac{\ell}{2}$</span>. WLOG suppose <span class="math-container">$a_k$</span> is this <span class="math-container">$a_i$</span>. Then I claim the packing problem instance <span class="math-container">$(a_1, \ldots, a_{k-1}), \ell+a_k$</span> is equivalent to the original instance. Notice that the value <span class="math-container">$s$</span> remains the same in both instances. </p>

<p>Certainly if you can pack the numbers <span class="math-container">$a_1, \ldots, a_k$</span> into three groups with each group having sum at most <span class="math-container">$s$</span> then you can pack the numbers <span class="math-container">$a_1, \ldots, a_{k-1}$</span> into three groups with each group having sum at most <span class="math-container">$s$</span>. </p>

<p>On the other hand, suppose you can pack the numbers <span class="math-container">$a_1, \ldots, a_{k-1}$</span> into three groups with each group having sum at most <span class="math-container">$s$</span>. For each of the three groups, consider the value <span class="math-container">$s$</span> minus the sum of the elements in the group. Call these values <span class="math-container">$e_1, e_2, e_3$</span>; here <span class="math-container">$e_i$</span> is the amount of "empty space" in group <span class="math-container">$i$</span>. We know that <span class="math-container">$e_1 + e_2 + e_3$</span>, the total empty space, is equal to <span class="math-container">$3s - \sum_{i = 1}^{k-1}a_i$</span> (total space <span class="math-container">$3s$</span> minus space used <span class="math-container">$\sum_{i = 1}^{k-1}a_i$</span>). But <span class="math-container">$3s - \sum_{i = 1}^{k-1}a_i = a_k + \ell$</span> by the definition of <span class="math-container">$s$</span>. Thus, the three groups have <span class="math-container">$a_k + \ell$</span> empty space in total. Then since <span class="math-container">$a_k &lt; \frac{\ell}{2}$</span>, we know that the total empty space is more than <span class="math-container">$3a_k$</span>. By the pigeon hole principle, at least one of the groups has <span class="math-container">$a_k$</span> or more empty space in it. Thus, we can add element <span class="math-container">$a_k$</span> to one of the groups and end up with a packing of the numbers <span class="math-container">$a_1, \ldots, a_k$</span> into three groups with each group having sum at most <span class="math-container">$s$</span>.</p>

<p>Thus, in order to solve your problem, it is sufficient to solve just the packing problem with no small numbers.</p>

<h2>Lemma 1</h2>

<p>Lemma statement:</p>

<p>Suppose we can partition <span class="math-container">$a_1, \ldots, a_k$</span> into groups 1 and 2 such that group 2 has an even number of elements and the sum of the elements in group 1 is in the interval <span class="math-container">$\left[s - \frac{\ell}{2}, s\right]$</span>. Then it is possible to further partition group 2 into two subgroups 2a and 2b each of which has sum at most <span class="math-container">$s$</span>. Notice that groups 1, 2a, and 2b are a solution of the packing problem instance.</p>

<p>Here's a proof.</p>

<p>Tentatively assign half of the elements of group 2 to subgroup 2a and the other half to subgroup 2b. Create a matching between the elements of the two subgroups. Swap these pairs between the two groups, one pair at a time. If there are <span class="math-container">$2n$</span> elements in group 2 then this process passes through exactly <span class="math-container">$n+1$</span> possible partitions of group 2 into subgroups 2a and 2b. I claim that at least one of those partitions has both subgroups with sum less than <span class="math-container">$s$</span>. </p>

<p>Let <span class="math-container">$S_{2a}$</span> and <span class="math-container">$S_{2b}$</span> be the sums of the two subgroups (we allow these values to change as the groups change). </p>

<p>At each step of the above process, group 2a gains one element and loses another. Since each element has value between <span class="math-container">$\frac{\ell}{2}$</span> and <span class="math-container">$\ell$</span>, we can conclude that at each step of the above process, <span class="math-container">$S_{2a}$</span> changes by at most <span class="math-container">$\frac{\ell}{2}$</span>. </p>

<p>Also, the final value of <span class="math-container">$S_{2a}$</span> is equal to the initial value of <span class="math-container">$S_{2b}$</span> since by the end of the process the groups have entirely swapped.</p>

<p>Let <span class="math-container">$A$</span> be the average value of <span class="math-container">$S_{2a}$</span> and <span class="math-container">$S_{2b}$</span>. Note that this is constant as the groups change. We know that the initial and final values of <span class="math-container">$S_{2a}$</span> average to <span class="math-container">$A$</span> (since the initial and final values of <span class="math-container">$S_{2a}$</span> equal the initial values of <span class="math-container">$S_{2a}$</span> and <span class="math-container">$S_{2b}$</span>). Thus, <span class="math-container">$A$</span> must be between the initial and final values of <span class="math-container">$S_{2a}$</span>. As we change the groups, the value of <span class="math-container">$S_{2a}$</span> takes steps of size at most <span class="math-container">$\frac{\ell}{2}$</span> from one side of <span class="math-container">$A$</span> to the other. From this, we can conclude that at some point, the value of <span class="math-container">$S_{2a}$</span> must be within half of the maximum step size (<span class="math-container">$\frac{\ell}{4}$</span>) of <span class="math-container">$A$</span>. Since <span class="math-container">$S_{2b}$</span> always has the same distance from <span class="math-container">$A$</span> as <span class="math-container">$S_{2a}$</span>, we can conclude that at some point, both sums <span class="math-container">$S_{2a}$</span> and <span class="math-container">$S_{2b}$</span> are within <span class="math-container">$\frac{\ell}{4}$</span> of <span class="math-container">$A$</span>. </p>

<p><span class="math-container">$3s - \ell - (S_{2a} + S_{2b})$</span> is the sum of the elements of group 1; thus, <span class="math-container">$3s - \ell - (S_{2a} + S_{2b}) \ge s - \frac{\ell}{2}$</span> (by the condition on the sum of group 1). Rearranging, we have that <span class="math-container">$(S_{2a} + S_{2b}) \le 2s - \frac{\ell}{2}$</span>. Therefore, the average of <span class="math-container">$S_{2a}$</span> and <span class="math-container">$S_{2b}$</span> is at most <span class="math-container">$s - \frac{\ell}{4}$</span>. Then at the time that both <span class="math-container">$S_{2a}$</span> and <span class="math-container">$S_{2b}$</span> are within <span class="math-container">$\frac{\ell}{4}$</span> of <span class="math-container">$A$</span>, we see that they are both at most <span class="math-container">$s$</span> as desired.</p>

<h2>Case 1: <span class="math-container">$k = 3n$</span></h2>

<p>Sum the <span class="math-container">$n$</span> smallest <span class="math-container">$a_i$</span>s and also the <span class="math-container">$n$</span> largest <span class="math-container">$a_i$</span>s.</p>

<p>If the <span class="math-container">$n$</span> smallest <span class="math-container">$a_i$</span>s sum to more than <span class="math-container">$s$</span>, then no group can have <span class="math-container">$n$</span> or more elements (as any choice of <span class="math-container">$n$</span> elements will result in the sum being too large). But the pigeon hole principle tells us that at least one group has at least <span class="math-container">$n$</span> elements. Thus, in this case there is no solution to the packing problem instance.</p>

<p>If the <span class="math-container">$n$</span> largest <span class="math-container">$a_i$</span>s sum to at most <span class="math-container">$s$</span>, then every choice of <span class="math-container">$n$</span> elements has a sum of at most <span class="math-container">$s$</span>. In this case, simply partitioning the elements into three groups of equal size solves the packing problem instance.</p>

<p>The only remaining case is that the smallest <span class="math-container">$n$</span> elements sum to at most <span class="math-container">$s$</span> and the largest <span class="math-container">$n$</span> elements sum to more than <span class="math-container">$s$</span>. As in the lemma, we can slowly transition between these two sets: start with a group initialized with the smallest <span class="math-container">$n$</span> elements and swap elements until the group has the largest <span class="math-container">$n$</span> elements. Each step moves the sum of the group by at most <span class="math-container">$\frac{\ell}{2}$</span> (by the same logic as in the proof of the lemma) and the sum crosses the value <span class="math-container">$s$</span> at some point in this process. Therefore, either immediately before or immediately after crossing the value <span class="math-container">$s$</span>, the sum is less than <span class="math-container">$s$</span> but less by at most <span class="math-container">$\frac{\ell}{2}$</span>. In other words, at some point in this process, the group has a sum in the interval <span class="math-container">$[s-\frac{\ell}{2}, s]$</span>. Take that group as group 1 and the remaining <span class="math-container">$2n$</span> elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.</p>

<h2>Case 2: <span class="math-container">$k = 3n+1$</span></h2>

<p>Sum the <span class="math-container">$n+1$</span> smallest <span class="math-container">$a_i$</span>s and also the <span class="math-container">$n+1$</span> largest <span class="math-container">$a_i$</span>s.</p>

<p>If the <span class="math-container">$n+1$</span> smallest <span class="math-container">$a_i$</span>s sum to more than <span class="math-container">$s$</span>, then no group can have <span class="math-container">$n+1$</span> or more elements (as any choice of <span class="math-container">$n+1$</span> elements will result in the sum being too large). But the pigeon hole principle tells us that at least one group has at least <span class="math-container">$n+1$</span> elements. Thus, in this case there is no solution to the packing problem instance.</p>

<p>If the <span class="math-container">$n+1$</span> largest <span class="math-container">$a_i$</span>s sum to at most <span class="math-container">$s$</span>, then every choice of <span class="math-container">$n+1$</span> elements has a sum of at most <span class="math-container">$s$</span>. In this case, simply partitioning the elements into three groups of size <span class="math-container">$n$</span>, <span class="math-container">$n$</span>, and <span class="math-container">$n+1$</span> solves the packing problem instance.</p>

<p>The only remaining case is that the smallest <span class="math-container">$n+1$</span> elements sum to at most <span class="math-container">$s$</span> and the largest <span class="math-container">$n+1$</span> elements sum to more than <span class="math-container">$s$</span>. As in the previous case, we can slowly transition between these two sets: start with a group initialized with the smallest <span class="math-container">$n+1$</span> elements and swap elements until the group has the largest <span class="math-container">$n+1$</span> elements. Each step moves the sum of the group by at most <span class="math-container">$\frac{\ell}{2}$</span> (by the same logic as in the proof of the lemma) and the sum crosses the value <span class="math-container">$s$</span> at some point in this process. Therefore, either immediately before or immediately after crossing the value <span class="math-container">$s$</span>, the sum is less than <span class="math-container">$s$</span> but less by at most <span class="math-container">$\frac{\ell}{2}$</span>. In other words, at some point in this process, the group has a sum in the interval <span class="math-container">$[s-\frac{\ell}{2}, s]$</span>. Take that group as group 1 and the remaining <span class="math-container">$2n$</span> elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.</p>

<h2>Case 3: <span class="math-container">$k = 3n+2$</span> first easy subcase</h2>

<p>Sum the <span class="math-container">$n$</span> smallest <span class="math-container">$a_i$</span>s and the <span class="math-container">$n$</span> largest <span class="math-container">$a_i$</span>s.</p>

<p>If either value is in the interval <span class="math-container">$[s-\frac{\ell}{2}, s]$</span>, immediately apply the lemma with that choice of <span class="math-container">$n$</span> elements as group 1 and the remaining <span class="math-container">$2n+2$</span> elements as group 2. This allows us to find a solution to the packing problem instance.</p>

<p>If the <span class="math-container">$n$</span> smallest <span class="math-container">$a_i$</span>s sum to less than <span class="math-container">$s-\frac{\ell}{2}$</span> and the <span class="math-container">$n$</span> largest <span class="math-container">$a_i$</span>s sum to more than <span class="math-container">$s$</span> then we can start with the <span class="math-container">$n$</span> smallest <span class="math-container">$a_i$</span>s and swap elements until we end up with the <span class="math-container">$n$</span> largest <span class="math-container">$a_i$</span>s. At each step the sum moves at most <span class="math-container">$\frac{\ell}{2}$</span>, so at some point in this process we have a group of <span class="math-container">$n$</span> elements whose sum is in the interval <span class="math-container">$[s-\frac{\ell}{2}, s]$</span>. Take that group as group 1 and the remaining <span class="math-container">$2n+2$</span> elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.</p>

<p>If the <span class="math-container">$n$</span> smallest <span class="math-container">$a_i$</span>s sum to more than <span class="math-container">$s$</span>, then no group can have <span class="math-container">$n$</span> or more elements (as any choice of <span class="math-container">$n$</span> elements will result in the sum being too large). But the pigeon hole principle tells us that at least one group has at least <span class="math-container">$n+1$</span> elements. Thus, in this case there is no solution to the packing problem instance.</p>

<p>The only remaining case is that both the <span class="math-container">$n$</span> smallest and <span class="math-container">$n$</span> largest <span class="math-container">$a_i$</span>s add to less than <span class="math-container">$s-\frac{\ell}{2}$</span>.</p>

<h2>Case 3: <span class="math-container">$k = 3n+2$</span> second easy subcase</h2>

<p>Sum the <span class="math-container">$n+2$</span> smallest <span class="math-container">$a_i$</span>s and the <span class="math-container">$n+2$</span> largest <span class="math-container">$a_i$</span>s.</p>

<p>If either value is in the interval <span class="math-container">$[s-\frac{\ell}{2}, s]$</span>, immediately apply the lemma with that choice of <span class="math-container">$n+2$</span> elements as group 1 and the remaining <span class="math-container">$2n$</span> elements as group 2. This allows us to find a solution to the packing problem instance.</p>

<p>If the <span class="math-container">$n+2$</span> smallest <span class="math-container">$a_i$</span>s sum to less than <span class="math-container">$s-\frac{\ell}{2}$</span> and the <span class="math-container">$n+2$</span> largest <span class="math-container">$a_i$</span>s sum to more than <span class="math-container">$s$</span> then we can start with the <span class="math-container">$n+2$</span> smallest <span class="math-container">$a_i$</span>s and swap elements until we end up with the <span class="math-container">$n+2$</span> largest <span class="math-container">$a_i$</span>s. At each step the sum moves at most <span class="math-container">$\frac{\ell}{2}$</span>, so at some point in this process we have a group of <span class="math-container">$n+2$</span> elements whose sum is in the interval <span class="math-container">$[s-\frac{\ell}{2}, s]$</span>. Take that group as group 1 and the remaining <span class="math-container">$2n$</span> elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.</p>

<p>If the <span class="math-container">$n+2$</span> largest <span class="math-container">$a_i$</span>s sum to at most <span class="math-container">$s$</span>, then every choice of <span class="math-container">$n+2$</span> elements has a sum of at most <span class="math-container">$s$</span>. In this case, simply partitioning the elements into three groups of size <span class="math-container">$n$</span>, <span class="math-container">$n+1$</span>, and <span class="math-container">$n+1$</span> solves the packing problem instance.</p>

<p>The only remaining case is that both the <span class="math-container">$n+2$</span> smallest and <span class="math-container">$n+2$</span> largest <span class="math-container">$a_i$</span>s add to more than <span class="math-container">$s$</span>.</p>

<h2>Case 3: <span class="math-container">$k = 3n+2$</span> hard subcase</h2>

<p>Suppose neither of the above two subcases handled the instance. Then we know the following:</p>

<ul>
<li>both the <span class="math-container">$n$</span> smallest and <span class="math-container">$n$</span> largest <span class="math-container">$a_i$</span>s add to less than <span class="math-container">$s-\frac{\ell}{2}$</span>.</li>
<li>both the <span class="math-container">$n+2$</span> smallest and <span class="math-container">$n+2$</span> largest <span class="math-container">$a_i$</span>s add to more than <span class="math-container">$s$</span>.</li>
</ul>

<p>Since the <span class="math-container">$n+2$</span> smallest <span class="math-container">$a_i$</span>s add to more than <span class="math-container">$s$</span>, no group can have <span class="math-container">$n+2$</span> or more elements. The only way this is possible to accomplish is if the groups have sizes <span class="math-container">$n$</span>, <span class="math-container">$n+1$</span>, and <span class="math-container">$n+1$</span>. </p>

<p>Note that since the <span class="math-container">$n$</span> largest <span class="math-container">$a_i$</span>s add to less than <span class="math-container">$s-\frac{\ell}{2}$</span>, it doesn't matter what elements are in the group of size <span class="math-container">$n$</span>: that group will have sum less than <span class="math-container">$s$</span> anyway. Clearly, we can modify any solution by swapping the <span class="math-container">$n$</span> largest <span class="math-container">$a_i$</span>s into the group of size <span class="math-container">$n$</span>. These swaps only decrease the sums of the other two groups, so there exists a solution to the packing problem instance if and only if there exists a solution in which the <span class="math-container">$n$</span> largest <span class="math-container">$a_i$</span>s form one of the groups.</p>

<p>Thus, the task at hand is simply this: is it possible to partition the <span class="math-container">$2n+2$</span> smallest <span class="math-container">$a_i$</span>s into two groups of size <span class="math-container">$n+1$</span> such that each of those two groups has sum at most <span class="math-container">$s$</span>. WLOG suppose that the <span class="math-container">$a_i$</span>s are in increasing order so that the <span class="math-container">$2n+2$</span> smallest <span class="math-container">$a_i$</span>s are <span class="math-container">$a_1, \ldots, a_{2n+2}$</span></p>

<p>Let <span class="math-container">$v$</span> be the average of the <span class="math-container">$n$</span> largest <span class="math-container">$a_i$</span>s. Let <span class="math-container">$x_i = v - a_i$</span> for each <span class="math-container">$i$</span>. Then <span class="math-container">$3s = \ell + \sum_{i = 1}^{3n+2}a_i = \ell + \sum_{i = 1}^{2n+2}a_i + \sum_{i = 2n+2}^{3n+2}a_i = \ell + \sum_{i = 1}^{2n+2}(v - x_i) + nv = \ell + (3n+2)v - \sum_{i = 1}^{2n+2}(x_i) = (\ell-v) + (3n+3)v - \sum_{i = 1}^{2n+2}(x_i)$</span>. </p>

<p>Then <span class="math-container">$s = (n+1)v + \frac{\ell - v}{3} - \frac{1}{3}\sum_{i = 1}^{2n+2}(x_i)$</span>.</p>

<p>If we choose some set <span class="math-container">$I$</span> of <span class="math-container">$n+1$</span> indices, then the sum of the <span class="math-container">$a_i$</span>s with <span class="math-container">$i \in I$</span> is equal to <span class="math-container">$\sum_{i\in I}a_i=\sum_{i\in I}v - x_i = (n+1)v-\sum_{i\in I}x_i$</span>. A set of indices <span class="math-container">$I$</span> is a valid choice for one of the groups provided this sum is at most <span class="math-container">$s$</span>. In other words, using the alternate definition of <span class="math-container">$s$</span> derived above, the condition we are interested in is <span class="math-container">$\sum_{i\in I}x_i \ge \frac{1}{3}\sum_{i = 1}^{2n+2}(x_i) - \frac{\ell - v}{3}$</span>. Obviously, the remaining <span class="math-container">$n+1$</span> indices <span class="math-container">$I' = \{1,\ldots, 2n+2\} \setminus I$</span> must also satisfy this condition: <span class="math-container">$\sum_{i\in I'}x_i \ge \frac{1}{3}\sum_{i = 1}^{2n+2}(x_i) - \frac{\ell - v}{3}$</span>. Since <span class="math-container">$\sum_{i\in I'}x_i = \sum_{i = 1}^{2n+2}x_i - \sum_{i\in I}x_i$</span>, we can rewrite the second condition as <span class="math-container">$\sum_{i\in I}x_i \le \frac{2}{3}\sum_{i = 1}^{2n+2}(x_i) + \frac{\ell - v}{3}$</span>. </p>

<p>Thus we have restated this subproblem using an equivalent alternative: we are trying to choose a set <span class="math-container">$I$</span> of <span class="math-container">$n+1$</span> indices among <span class="math-container">$\{1, \ldots, 2n+2\}$</span> such that <span class="math-container">$\frac{2}{3}\sum_{i = 1}^{2n+2}(x_i) + \frac{\ell - v}{3} \ge \sum_{i\in I}x_i \ge \frac{1}{3}\sum_{i = 1}^{2n+2}(x_i) - \frac{\ell - v}{3}$</span>.</p>

<p>Note that <span class="math-container">$\ell \ge v$</span> (and therefore <span class="math-container">$\ell-v \ge 0$</span>) since <span class="math-container">$v$</span> is the average of some <span class="math-container">$a_i$</span>s and <span class="math-container">$\ell$</span> is an upper bound on all <span class="math-container">$a_i$</span>s. Let <span class="math-container">$X = \sum_{i = 1}^{2n+2}(x_i)$</span>. Our condition above can be rewritten as follows: choose a set <span class="math-container">$I$</span> of <span class="math-container">$n+1$</span> indices among <span class="math-container">$\{1, \ldots, 2n+2\}$</span> such that <span class="math-container">$\sum_{i\in I}x_i$</span> is in the interval <span class="math-container">$[cX, (1-c)X]$</span> where <span class="math-container">$c = \frac{1}{3} - \frac{\ell - v}{3X} \le \frac{1}{3}$</span>.</p>

<p>Suppose that for some <span class="math-container">$j$</span>, <span class="math-container">$x_j$</span> has value at least <span class="math-container">$\frac{X}{3}$</span>. In this case, let <span class="math-container">$I$</span> consist of the index <span class="math-container">$j$</span> and also of the <span class="math-container">$n-1$</span> indices corresponding to the smallest <span class="math-container">$x_i$</span>s. If these <span class="math-container">$x_i$</span>s add to at most <span class="math-container">$(1-c)X$</span> then this choice of <span class="math-container">$I$</span> satisfies the above constraint: the sum <span class="math-container">$\sum_{i\in I}x_i$</span> is at least <span class="math-container">$x_j \ge \frac{X}{3} = \frac{1}{3}X \ge cX$</span> and at most <span class="math-container">$(1-c)X$</span>. Thus, this set of indices <span class="math-container">$I$</span> can be used to select one of the groups of size <span class="math-container">$n+1$</span> in a solution to the packing problem instance. On the other hand, if these <span class="math-container">$x_i$</span>s add to more than <span class="math-container">$(1-c)X$</span> then the instance cannot be solved: one of the two halves will include <span class="math-container">$x_j$</span> and the sum of that half is always going to be more than <span class="math-container">$(1-c)X$</span> (since it was more than that even when we put the smallest elements with <span class="math-container">$x_j$</span>).</p>

<p>Thus, we have handled the case that some <span class="math-container">$x_j$</span> has value at least <span class="math-container">$\frac{X}{3}$</span>. The remaining case is that every <span class="math-container">$x_i$</span> has value at most <span class="math-container">$\frac{X}{3}$</span>. Then assign the <span class="math-container">$x_i$</span>s to two groups, 1 and 2, arbitrarily. Create a matching of the elements of the two groups and swap those pairs one pair at a time. Over the course of this process, the sum of the elements of group 1 will move from it's initial sum to the initial sum of group 2's elements. In other words, the sum of group 1 will cross the average value <span class="math-container">$\frac{X}{2}$</span>. Each step in this process involves group 1 losing an <span class="math-container">$x_i$</span> and gaining one; since the <span class="math-container">$x_i$</span>s have value at most <span class="math-container">$\frac{X}{3}$</span>, a pair of <span class="math-container">$x_i$</span>s differs by at most <span class="math-container">$\frac{X}{3}$</span> and so each step moves the sum of group 1 by at most <span class="math-container">$\frac{X}{3}$</span>. Thus, there will be some point in the process when the sum of group 1 is within half the maximum step size of the average. Thus, at some point the sum of group 1 will fall within <span class="math-container">$\frac{X}{2} \pm \frac{X}{6}$</span>. But this is the interval <span class="math-container">$[\frac{1}{3}X, \frac{2}{3}X]$</span>, which is a subinterval of <span class="math-container">$[cX, (1-c)X]$</span>. Thus, at some point during this process, the group 1 at the time will satisfy our desired condition. We can use this group of <span class="math-container">$x_i$</span>s to select a corresponding group of <span class="math-container">$a_i$</span>s; these <span class="math-container">$a_i$</span>s form one of the two groups of size <span class="math-container">$n+1$</span> needed to solve the packing problem instance.</p>

<h2>Conclusion</h2>

<p>The above exhaustive casework can be used as an algorithm to partition a list into three groups of the same sum using one soft number. The casework will also identify when this is impossible. The runtime of this algorithm is polynomial.</p>

CC BY-SA 4.0
2019-02-05T17:03:07.617Z
Thanks!  Lemma 1 proof can be shortened: order group 2's elements by increasing order. Let group 2a be the odd-indexed elements and group 2b the even-indexed elements. Each element in 2a is smaller than the next element which is in 2b, so $S_{2b} \geq S_{2a}$. On the other hand, if we remove the smallest element from 2a and the largest element from 2b, the sum of elements remaining in 2a is at least the sum of elements remaining in 2b. So $S_{2b}-S_{2a}\leq$ the largest minus smallest element = $l/2$. By the assumption, $S_{2b}+S_{2a}\leq 2s-l/2$. Summing the inequalities gives $S_{2b}\leq s$.
Erel Segal-Halevi
CC BY-SA 4.0
2019-02-05T17:06:08.873Z
Question: you mention a sub-problem: "is it possible to partition the $2n+2$ smallest $a_i$-s into two groups of size $n+1$ such that each of those two groups has sum at most $s$?". Why is this problem not as hard as the PARTITION problem?
Erel Segal-Halevi
CC BY-SA 4.0
2019-02-05T17:13:07.450Z
You're right, my Lemma 1 proof is not the simplest possible. I'm a bit too lazy to put in the edits though (especially since other parts of the proof reference the techniques used in the proof). As for the sub-problem, the reason it is not as hard as PARTITION is that you don't actually have to solve that subproblem in full generality: the value of $s$ is not arbitrary. In order to fall into that case, there are specific additional constraints on $s$ and on the $a_i$s that must hold. If these constraints were missing, you would be right: the problem would be as hard as PARTITION.
Mikhail Rudoy
CC BY-SA 4.0
2019-02-06T22:37:52.973Z
Thanks a lot for the clear and detailed solution.
Erel Segal-Halevi
CC BY-SA 4.0
2019-04-18T04:36:55.807Z
Hi Mikhail, we are working on a paper in which this result is useful. Would you like to join? If so then please write me an email.
Erel Segal-Halevi
CC BY-SA 4.0
2019-02-04T02:09:06.813Z
2019-02-04T02:25:59.823Z
2019-02-04T02:25:59.823Z
Mikhail Rudoy
<p><strong>Edit:</strong> The result is incorrect, see the discussion at the end. </p>

<p>Inspired by Mikhail Rudoy's answer, we can generalize to partitioning into <span class="math-container">$k$</span> parts with equal sum. The problem is polynomial time solvable for each constant <span class="math-container">$k$</span>. </p>

<p>The input is <span class="math-container">$a_1,\ldots,a_n$</span> such that <span class="math-container">$a_n$</span> is the largest number.
Mikhail's observations are, wlog,</p>

<ul>
<li>the soft number is <span class="math-container">$a_n$</span></li>
<li><span class="math-container">$a_i&gt;\frac{a_n}{k-1}$</span> for each <span class="math-container">$i$</span></li>
</ul>

<p>wlog, assume that the sum of <span class="math-container">$a_1,\ldots,a_{n-1}$</span> is <span class="math-container">$1$</span> (that is, <span class="math-container">$1=ks-a_n$</span>).
Note that <span class="math-container">$a_n \geq \frac{1}{n-1}$</span>, so <span class="math-container">$a_i &gt; \frac{1}{(k-1)(n-1)}&gt;\frac{1}{kn}$</span> for each <span class="math-container">$i$</span>. The problem is equivalent to partitioning the numbers <span class="math-container">$a_1,\ldots,a_{n-1}$</span> into <span class="math-container">$k$</span> subsets such that the sum of each subset is at most <span class="math-container">$s := \frac{1+a_n}{k}$</span>.</p>

<p>We consider a restriction of the <a href="https://en.wikipedia.org/wiki/Multiple_knapsack_problem" rel="nofollow noreferrer">multiple knapsack problem</a>.
Define the <em><span class="math-container">$k$</span>-knapsack problem</em> as an instance of the multiple knapsack problem with <span class="math-container">$k$</span> knapsacks of the same capacity, where the value of each item equals the weight of the item.</p>

<p>Let the input for the <span class="math-container">$k$</span>-knapsack problem be <span class="math-container">$a_1,\ldots,a_{n-1}$</span>, and each knapsack has capacity <span class="math-container">$s$</span>. The following claim is clear.</p>

<p><em>Claim</em>: A <span class="math-container">$(1-\frac{1}{kn})$</span>-approximation algorithm for the <span class="math-container">$k$</span>-knapsack problem returns <span class="math-container">$1$</span>, if and only if all the numbers <span class="math-container">$a_1,\ldots,a_{n-1}$</span> can be packed into the <span class="math-container">$k$</span> knapsacks.</p>

<p>By the above claim, we just have to find a <span class="math-container">$(1-\frac{1}{kn})$</span>-approximation algorithm for the <span class="math-container">$k$</span>-knapsack problem. </p>

<p><em>Claim</em>: There is a pseudopolynomial time algorithm for knapsack generalizes for <span class="math-container">$k$</span>-knapsack for each constant <span class="math-container">$k$</span>.</p>

<p><em>Proof</em>: Define <span class="math-container">$D[b_1,\ldots,b_k,i]$</span> to be the maximum value using elements <span class="math-container">$a_1,\ldots,a_i$</span>, where the knapsack has capacity <span class="math-container">$b_1,\ldots,b_k$</span>. The recurrence relation is <span class="math-container">$D[b_1,\ldots,b_k,i+1] = \max( \max_{j} (D[b_1,\ldots,b_j-a_{i+1},b_k,i])+a_{i+1},D[b_1,\ldots,b_k,i])$</span>. The base case are simple. 
The running times is <span class="math-container">$O(s^kkn)$</span>.</p>

<p><del>It is standard to obtain an FPTAS by scaling all numbers and round to integers, <a href="http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf" rel="nofollow noreferrer">see section 5 of this</a>. This means we can find a <span class="math-container">$(1-\frac{1}{kn})$</span>-approximation to <span class="math-container">$k$</span>-knapsack problem in polynomial time.
Therefore for each constant <span class="math-container">$k$</span>, the original problem can be decided in polynomial time. </del></p>

<p>The above is incorrect, due to the pseudopolynomial time algorithm does not transform into an FPTAS. However, the approach might still give us some insight because we have a very special case of <span class="math-container">$k$</span>-knapsack problem.</p>

CC BY-SA 4.0
2019-02-06T19:06:10.037Z
I found this paper: https://epubs.siam.org/doi/abs/10.1137/S0097539700382820 which shows a PTAS for multple-knapsack. How do you obtain an FPTAS from it? (did you mean that there is an FPTAS for the special case in which the values are equal to the weights?)
Erel Segal-Halevi
CC BY-SA 4.0
2019-02-06T20:04:45.300Z
I have made an update. The FPTAS is for the case when $k$ is a constant. If the number of knapsacks is part of the input, there is no FPTAS.
Chao Xu
CC BY-SA 4.0
2019-04-18T04:36:30.273Z
Hi Chao, we are working on a paper in which this result is useful. Would you like to join? If so then please write me an email.
Erel Segal-Halevi
CC BY-SA 4.0
2019-02-04T10:14:10.963Z
2019-06-05T23:54:48.637Z
2019-06-05T23:54:48.637Z
Chao Xu
<p>This answer does <strong>not</strong> solve the question.
It only settles the following auxiliary problem formulated by @JohnDvorak in the comments (partitioning a set in 1:2 ratio):</p>

<blockquote>
  <p><strong>Auxiliary problem:</strong><br>
  <strong>Instance:</strong> Positive rationals <span class="math-container">$a_1,\ldots,a_m$</span> with <span class="math-container">$\sum_{i=1}^m a_i = 3A$</span>.<br>
  <strong>Question:</strong> Does there exist an index set <span class="math-container">$I\subseteq\{1,\ldots,n\}$</span> with <span class="math-container">$\sum_{i\in I}a_i=A$</span>?</p>
</blockquote>

<ul>
<li>Take an instance of classical PARTITION (rationals <span class="math-container">$b_1,\ldots,b_n$</span> with sum <span class="math-container">$2B$</span>, can you split them into two groups with sum <span class="math-container">$B$</span>).</li>
<li>Take <span class="math-container">$b_1,\ldots,b_n$</span> together with the four numbers <span class="math-container">$5B,5B,5B,7B$</span> to create an instance of the auxiliary problem. The sum of all <span class="math-container">$n+4$</span> numbers then is <span class="math-container">$24B$</span>, so that <span class="math-container">$A=8B$</span>.</li>
<li>Splitting the <span class="math-container">$n+4$</span> numbers into a group with sum <span class="math-container">$A=8B$</span> and a group with sum <span class="math-container">$2A=16B$</span> is possible if and only if the PARTITION instance has answer YES.</li>
</ul>

<p>Hence @JohnDvorak's auxiliary problem is NP-complete</p>

CC BY-SA 4.0
2019-04-18T07:26:18.833Z
Hi Gamow, we are working on a paper in which this result may be useful. Would you like to join? If so then please write me an email.
Erel Segal-Halevi
CC BY-SA 4.0
2019-01-27T16:31:15.603Z
2019-03-25T17:39:09.050Z
2019-03-25T17:39:09.050Z
Gamow
<p>In the standard <a href="https://en.wikipedia.org/wiki/Partition_problem" rel="nofollow noreferrer">partition problem</a>, we are given some numbers whose sum is <span class="math-container">$2s$</span> and have to decide whether they can be partitioned into two subset whose sum is <span class="math-container">$s$</span>. It is known to be NP-hard. </p>

<p>However, assume that we are allowed to designate one of the numbers to be a <em>"soft number"</em> that can be cut it into an arbitrary number of pieces, where different pieces may be put into different subsets. 
Then the problem becomes easy: just arrange all numbers on a line in an arbitrary order, and cut the line into two sub-lines with the same sum. </p>

<blockquote>
  <p>QUESTION: Suppose we are given some numbers whose sum is <span class="math-container">$3s$</span>, and have to decide whether they can be partitioned into <em>three</em> subsets whose sum is <span class="math-container">$s$</span>, while using at most <em>one</em> soft number. What is the complexity of this problem?</p>
</blockquote>

<ul>
<li>If we are allowed to use <em>two</em> soft numbers, then the problem is again easy - we can solve it by arranging the numbers on a line as above. </li>
<li>If we are allowed to use <em>zero</em> soft numbers, then the problem is obviously hard - it is at least as hard as the problem of partitioning into two subsets.</li>
<li>If we are allowed to use <em>one</em> soft number, my guess is that the problem should still be hard, and we can somehow reduce to it from the standard partition problem, but I could not find the right reduction. So, is it easy or hard?</li>
</ul>

<p>Another question: in case the problem is indeed NP-hard, can it be solved in pseudo-polynomial time like the two-subset partition problem?</p>

CC BY-SA 4.0
2019-01-27T08:16:43.223Z
A part of this problem is to find a subset whose sum is one third the sum of the whole set. However, I can't find the appropriate references saying this restricted subset-sum problem is NP-hard.
John Dvorak
CC BY-SA 4.0
2019-01-27T08:22:41.033Z
It's equivalent to that, actually, as the remainder is to bipartition the two thirds with one cut.
John Dvorak
CC BY-SA 4.0
2019-01-27T16:02:29.783Z
@JohnDvorak if we can solve the subset-sum problem then we can solve the problem in the question, but the opposite is not true: we may have a solution to the problem in question in which one number is cut into three fractions, and each subset contains one fraction. This solution does not solve the subset-sum problem.
Erel Segal-Halevi
CC BY-SA 4.0
2019-01-27T16:06:00.247Z
which is why I didn't post an answer. I'm convinced that the 1:2 partition problem is still np-complete (and more generally the partition problem for any fixed ratio), but I don't have any proof for it. But if it is indeed NP-hard, then so is the 3-way partition with one cut problem.
John Dvorak
CC BY-SA 4.0
2019-01-27T16:37:40.967Z
I have updated the problem formulation so that it is clear that a cuttable number can be cut into many pieces. (When I first read the problem, I thought that you are only allowed to cut one number once.)
Gamow
<np-hardness><reductions><partition-problem>
A partition problem in which some numbers may be cut
Erel Segal-Halevi
# A partition problem in which some numbers may be cut

(Asked by: username_0 on 2019-01-27)

In the standard [partition problem](https://en.wikipedia.org/wiki/Partition_problem), we are given some numbers whose sum is $2s$ and have to decide whether they can be partitioned into two subset whose sum is $s$. It is known to be NP-hard.

However, assume that we are allowed to designate one of the numbers to be a *"soft number"* that can be cut it into an arbitrary number of pieces, where different pieces may be put into different subsets.
Then the problem becomes easy: just arrange all numbers on a line in an arbitrary order, and cut the line into two sub-lines with the same sum.

> QUESTION: Suppose we are given some numbers whose sum is $3s$, and have to decide whether they can be partitioned into *three* subsets whose sum is $s$, while using at most *one* soft number. What is the complexity of this problem?

* If we are allowed to use *two* soft numbers, then the problem is again easy - we can solve it by arranging the numbers on a line as above.
* If we are allowed to use *zero* soft numbers, then the problem is obviously hard - it is at least as hard as the problem of partitioning into two subsets.
* If we are allowed to use *one* soft number, my guess is that the problem should still be hard, and we can somehow reduce to it from the standard partition problem, but I could not find the right reduction. So, is it easy or hard?

Another question: in case the problem is indeed NP-hard, can it be solved in pseudo-polynomial time like the two-subset partition problem?

**Tags:** np-hardness, reductions, partition-problem
> **Comments:**
> **username_1**: A part of this problem is to find a subset whose sum is one third the sum of the whole set. However, I can't find the appropriate references saying this restricted subset-sum problem is NP-hard.  
> **username_1**: It's equivalent to that, actually, as the remainder is to bipartition the two thirds with one cut.  
> **username_0**: @JohnDvorak if we can solve the subset-sum problem then we can solve the problem in the question, but the opposite is not true: we may have a solution to the problem in question in which one number is cut into three fractions, and each subset contains one fraction. This solution does not solve the subset-sum problem.  
> **username_1**: which is why I didn't post an answer. I'm convinced that the 1:2 partition problem is still np-complete (and more generally the partition problem for any fixed ratio), but I don't have any proof for it. But if it is indeed NP-hard, then so is the 3-way partition with one cut problem.  
> **username_2**: I have updated the problem formulation so that it is clear that a cuttable number can be cut into many pieces. (When I first read the problem, I thought that you are only allowed to cut one number once.)  

---

## 3 answers

### Answer by username_3 on 2019-02-04. Score: 5 | Accepted answer

## The largest number is the soft number

I claim that for any instance of your problem, if the instance is solvable (it is possible to partition the numbers using one soft number) then it is possible to solve the instance using the largest number as the sole soft number. This is easy to prove: any solution can be modified into a solution with the largest number as the soft number; simply place the number that is currently the soft number into the partition that contains the largest number and split the largest number among the parts of the partition instead.

## Packing problem

Here is a problem that I will call the packing problem:

The input consists of a list of positive numbers $a\_1, a\_2, \ldots, a\_k$ and one final number $\ell$ such that $\ell \ge a\_i$ for all $i$. Define $s = \frac{1}{3}\left(\ell + \sum\_{i = 1}^ka\_i\right)$. Then the problem is to partition the list of $a\_i$s into three parts such that each part has sum at most $s$.

I claim that the packing problem with inputs $a\_1, \ldots, a\_k$ and $\ell$ is equivalent to your problem with input list $a\_1, \ldots, a\_k, \ell$. If it's possible to pack the numbers $a\_1, \ldots, a\_k$ into three groups each of sum at most $s$ then you can use $\ell$ as a soft number to round out each of the sums to exactly $s$; thus you have a partition of $a\_1, \ldots, a\_k, \ell$ into three groups of sum $s$ using one soft number. If on the other hand $a\_1, \ldots, a\_k, \ell$ can be partitioned into three groups of sum $s$ using one soft number then the list can be partitioned into three groups of sum $s$ using $\ell$ as the soft number (by the result from the previous section). In this case the grouping of the $a\_i$s into three parts satisfies the condition that each part has sum at most $s$.

## The packing problem with no small numbers

Say that an instance of the packing problem "has no small numbers" if for every $i$, $a\_i > \frac{\ell}{2}$. I claim that you can reduce the packing problem to the packing problem with no small numbers.

Suppose that in packing problem instance $(a\_1, \ldots, a\_k), \ell$ some $a\_i$ has $a\_i \le \frac{\ell}{2}$. WLOG suppose $a\_k$ is this $a\_i$. Then I claim the packing problem instance $(a\_1, \ldots, a\_{k-1}), \ell+a\_k$ is equivalent to the original instance. Notice that the value $s$ remains the same in both instances.

Certainly if you can pack the numbers $a\_1, \ldots, a\_k$ into three groups with each group having sum at most $s$ then you can pack the numbers $a\_1, \ldots, a\_{k-1}$ into three groups with each group having sum at most $s$.

On the other hand, suppose you can pack the numbers $a\_1, \ldots, a\_{k-1}$ into three groups with each group having sum at most $s$. For each of the three groups, consider the value $s$ minus the sum of the elements in the group. Call these values $e\_1, e\_2, e\_3$; here $e\_i$ is the amount of "empty space" in group $i$. We know that $e\_1 + e\_2 + e\_3$, the total empty space, is equal to $3s - \sum\_{i = 1}^{k-1}a\_i$ (total space $3s$ minus space used $\sum\_{i = 1}^{k-1}a\_i$). But $3s - \sum\_{i = 1}^{k-1}a\_i = a\_k + \ell$ by the definition of $s$. Thus, the three groups have $a\_k + \ell$ empty space in total. Then since $a\_k < \frac{\ell}{2}$, we know that the total empty space is more than $3a\_k$. By the pigeon hole principle, at least one of the groups has $a\_k$ or more empty space in it. Thus, we can add element $a\_k$ to one of the groups and end up with a packing of the numbers $a\_1, \ldots, a\_k$ into three groups with each group having sum at most $s$.

Thus, in order to solve your problem, it is sufficient to solve just the packing problem with no small numbers.

## Lemma 1

Lemma statement:

Suppose we can partition $a\_1, \ldots, a\_k$ into groups 1 and 2 such that group 2 has an even number of elements and the sum of the elements in group 1 is in the interval $\left[s - \frac{\ell}{2}, s\right]$. Then it is possible to further partition group 2 into two subgroups 2a and 2b each of which has sum at most $s$. Notice that groups 1, 2a, and 2b are a solution of the packing problem instance.

Here's a proof.

Tentatively assign half of the elements of group 2 to subgroup 2a and the other half to subgroup 2b. Create a matching between the elements of the two subgroups. Swap these pairs between the two groups, one pair at a time. If there are $2n$ elements in group 2 then this process passes through exactly $n+1$ possible partitions of group 2 into subgroups 2a and 2b. I claim that at least one of those partitions has both subgroups with sum less than $s$.

Let $S\_{2a}$ and $S\_{2b}$ be the sums of the two subgroups (we allow these values to change as the groups change).

At each step of the above process, group 2a gains one element and loses another. Since each element has value between $\frac{\ell}{2}$ and $\ell$, we can conclude that at each step of the above process, $S\_{2a}$ changes by at most $\frac{\ell}{2}$.

Also, the final value of $S\_{2a}$ is equal to the initial value of $S\_{2b}$ since by the end of the process the groups have entirely swapped.

Let $A$ be the average value of $S\_{2a}$ and $S\_{2b}$. Note that this is constant as the groups change. We know that the initial and final values of $S\_{2a}$ average to $A$ (since the initial and final values of $S\_{2a}$ equal the initial values of $S\_{2a}$ and $S\_{2b}$). Thus, $A$ must be between the initial and final values of $S\_{2a}$. As we change the groups, the value of $S\_{2a}$ takes steps of size at most $\frac{\ell}{2}$ from one side of $A$ to the other. From this, we can conclude that at some point, the value of $S\_{2a}$ must be within half of the maximum step size ($\frac{\ell}{4}$) of $A$. Since $S\_{2b}$ always has the same distance from $A$ as $S\_{2a}$, we can conclude that at some point, both sums $S\_{2a}$ and $S\_{2b}$ are within $\frac{\ell}{4}$ of $A$.

$3s - \ell - (S\_{2a} + S\_{2b})$ is the sum of the elements of group 1; thus, $3s - \ell - (S\_{2a} + S\_{2b}) \ge s - \frac{\ell}{2}$ (by the condition on the sum of group 1). Rearranging, we have that $(S\_{2a} + S\_{2b}) \le 2s - \frac{\ell}{2}$. Therefore, the average of $S\_{2a}$ and $S\_{2b}$ is at most $s - \frac{\ell}{4}$. Then at the time that both $S\_{2a}$ and $S\_{2b}$ are within $\frac{\ell}{4}$ of $A$, we see that they are both at most $s$ as desired.

## Case 1: $k = 3n$

Sum the $n$ smallest $a\_i$s and also the $n$ largest $a\_i$s.

If the $n$ smallest $a\_i$s sum to more than $s$, then no group can have $n$ or more elements (as any choice of $n$ elements will result in the sum being too large). But the pigeon hole principle tells us that at least one group has at least $n$ elements. Thus, in this case there is no solution to the packing problem instance.

If the $n$ largest $a\_i$s sum to at most $s$, then every choice of $n$ elements has a sum of at most $s$. In this case, simply partitioning the elements into three groups of equal size solves the packing problem instance.

The only remaining case is that the smallest $n$ elements sum to at most $s$ and the largest $n$ elements sum to more than $s$. As in the lemma, we can slowly transition between these two sets: start with a group initialized with the smallest $n$ elements and swap elements until the group has the largest $n$ elements. Each step moves the sum of the group by at most $\frac{\ell}{2}$ (by the same logic as in the proof of the lemma) and the sum crosses the value $s$ at some point in this process. Therefore, either immediately before or immediately after crossing the value $s$, the sum is less than $s$ but less by at most $\frac{\ell}{2}$. In other words, at some point in this process, the group has a sum in the interval $[s-\frac{\ell}{2}, s]$. Take that group as group 1 and the remaining $2n$ elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.

## Case 2: $k = 3n+1$

Sum the $n+1$ smallest $a\_i$s and also the $n+1$ largest $a\_i$s.

If the $n+1$ smallest $a\_i$s sum to more than $s$, then no group can have $n+1$ or more elements (as any choice of $n+1$ elements will result in the sum being too large). But the pigeon hole principle tells us that at least one group has at least $n+1$ elements. Thus, in this case there is no solution to the packing problem instance.

If the $n+1$ largest $a\_i$s sum to at most $s$, then every choice of $n+1$ elements has a sum of at most $s$. In this case, simply partitioning the elements into three groups of size $n$, $n$, and $n+1$ solves the packing problem instance.

The only remaining case is that the smallest $n+1$ elements sum to at most $s$ and the largest $n+1$ elements sum to more than $s$. As in the previous case, we can slowly transition between these two sets: start with a group initialized with the smallest $n+1$ elements and swap elements until the group has the largest $n+1$ elements. Each step moves the sum of the group by at most $\frac{\ell}{2}$ (by the same logic as in the proof of the lemma) and the sum crosses the value $s$ at some point in this process. Therefore, either immediately before or immediately after crossing the value $s$, the sum is less than $s$ but less by at most $\frac{\ell}{2}$. In other words, at some point in this process, the group has a sum in the interval $[s-\frac{\ell}{2}, s]$. Take that group as group 1 and the remaining $2n$ elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.

## Case 3: $k = 3n+2$ first easy subcase

Sum the $n$ smallest $a\_i$s and the $n$ largest $a\_i$s.

If either value is in the interval $[s-\frac{\ell}{2}, s]$, immediately apply the lemma with that choice of $n$ elements as group 1 and the remaining $2n+2$ elements as group 2. This allows us to find a solution to the packing problem instance.

If the $n$ smallest $a\_i$s sum to less than $s-\frac{\ell}{2}$ and the $n$ largest $a\_i$s sum to more than $s$ then we can start with the $n$ smallest $a\_i$s and swap elements until we end up with the $n$ largest $a\_i$s. At each step the sum moves at most $\frac{\ell}{2}$, so at some point in this process we have a group of $n$ elements whose sum is in the interval $[s-\frac{\ell}{2}, s]$. Take that group as group 1 and the remaining $2n+2$ elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.

If the $n$ smallest $a\_i$s sum to more than $s$, then no group can have $n$ or more elements (as any choice of $n$ elements will result in the sum being too large). But the pigeon hole principle tells us that at least one group has at least $n+1$ elements. Thus, in this case there is no solution to the packing problem instance.

The only remaining case is that both the $n$ smallest and $n$ largest $a\_i$s add to less than $s-\frac{\ell}{2}$.

## Case 3: $k = 3n+2$ second easy subcase

Sum the $n+2$ smallest $a\_i$s and the $n+2$ largest $a\_i$s.

If either value is in the interval $[s-\frac{\ell}{2}, s]$, immediately apply the lemma with that choice of $n+2$ elements as group 1 and the remaining $2n$ elements as group 2. This allows us to find a solution to the packing problem instance.

If the $n+2$ smallest $a\_i$s sum to less than $s-\frac{\ell}{2}$ and the $n+2$ largest $a\_i$s sum to more than $s$ then we can start with the $n+2$ smallest $a\_i$s and swap elements until we end up with the $n+2$ largest $a\_i$s. At each step the sum moves at most $\frac{\ell}{2}$, so at some point in this process we have a group of $n+2$ elements whose sum is in the interval $[s-\frac{\ell}{2}, s]$. Take that group as group 1 and the remaining $2n$ elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.

If the $n+2$ largest $a\_i$s sum to at most $s$, then every choice of $n+2$ elements has a sum of at most $s$. In this case, simply partitioning the elements into three groups of size $n$, $n+1$, and $n+1$ solves the packing problem instance.

The only remaining case is that both the $n+2$ smallest and $n+2$ largest $a\_i$s add to more than $s$.

## Case 3: $k = 3n+2$ hard subcase

Suppose neither of the above two subcases handled the instance. Then we know the following:

* both the $n$ smallest and $n$ largest $a\_i$s add to less than $s-\frac{\ell}{2}$.
* both the $n+2$ smallest and $n+2$ largest $a\_i$s add to more than $s$.

Since the $n+2$ smallest $a\_i$s add to more than $s$, no group can have $n+2$ or more elements. The only way this is possible to accomplish is if the groups have sizes $n$, $n+1$, and $n+1$.

Note that since the $n$ largest $a\_i$s add to less than $s-\frac{\ell}{2}$, it doesn't matter what elements are in the group of size $n$: that group will have sum less than $s$ anyway. Clearly, we can modify any solution by swapping the $n$ largest $a\_i$s into the group of size $n$. These swaps only decrease the sums of the other two groups, so there exists a solution to the packing problem instance if and only if there exists a solution in which the $n$ largest $a\_i$s form one of the groups.

Thus, the task at hand is simply this: is it possible to partition the $2n+2$ smallest $a\_i$s into two groups of size $n+1$ such that each of those two groups has sum at most $s$. WLOG suppose that the $a\_i$s are in increasing order so that the $2n+2$ smallest $a\_i$s are $a\_1, \ldots, a\_{2n+2}$

Let $v$ be the average of the $n$ largest $a\_i$s. Let $x\_i = v - a\_i$ for each $i$. Then $3s = \ell + \sum\_{i = 1}^{3n+2}a\_i = \ell + \sum\_{i = 1}^{2n+2}a\_i + \sum\_{i = 2n+2}^{3n+2}a\_i = \ell + \sum\_{i = 1}^{2n+2}(v - x\_i) + nv = \ell + (3n+2)v - \sum\_{i = 1}^{2n+2}(x\_i) = (\ell-v) + (3n+3)v - \sum\_{i = 1}^{2n+2}(x\_i)$.

Then $s = (n+1)v + \frac{\ell - v}{3} - \frac{1}{3}\sum\_{i = 1}^{2n+2}(x\_i)$.

If we choose some set $I$ of $n+1$ indices, then the sum of the $a\_i$s with $i \in I$ is equal to $\sum\_{i\in I}a\_i=\sum\_{i\in I}v - x\_i = (n+1)v-\sum\_{i\in I}x\_i$. A set of indices $I$ is a valid choice for one of the groups provided this sum is at most $s$. In other words, using the alternate definition of $s$ derived above, the condition we are interested in is $\sum\_{i\in I}x\_i \ge \frac{1}{3}\sum\_{i = 1}^{2n+2}(x\_i) - \frac{\ell - v}{3}$. Obviously, the remaining $n+1$ indices $I' = \{1,\ldots, 2n+2\} \setminus I$ must also satisfy this condition: $\sum\_{i\in I'}x\_i \ge \frac{1}{3}\sum\_{i = 1}^{2n+2}(x\_i) - \frac{\ell - v}{3}$. Since $\sum\_{i\in I'}x\_i = \sum\_{i = 1}^{2n+2}x\_i - \sum\_{i\in I}x\_i$, we can rewrite the second condition as $\sum\_{i\in I}x\_i \le \frac{2}{3}\sum\_{i = 1}^{2n+2}(x\_i) + \frac{\ell - v}{3}$.

Thus we have restated this subproblem using an equivalent alternative: we are trying to choose a set $I$ of $n+1$ indices among $\{1, \ldots, 2n+2\}$ such that $\frac{2}{3}\sum\_{i = 1}^{2n+2}(x\_i) + \frac{\ell - v}{3} \ge \sum\_{i\in I}x\_i \ge \frac{1}{3}\sum\_{i = 1}^{2n+2}(x\_i) - \frac{\ell - v}{3}$.

Note that $\ell \ge v$ (and therefore $\ell-v \ge 0$) since $v$ is the average of some $a\_i$s and $\ell$ is an upper bound on all $a\_i$s. Let $X = \sum\_{i = 1}^{2n+2}(x\_i)$. Our condition above can be rewritten as follows: choose a set $I$ of $n+1$ indices among $\{1, \ldots, 2n+2\}$ such that $\sum\_{i\in I}x\_i$ is in the interval $[cX, (1-c)X]$ where $c = \frac{1}{3} - \frac{\ell - v}{3X} \le \frac{1}{3}$.

Suppose that for some $j$, $x\_j$ has value at least $\frac{X}{3}$. In this case, let $I$ consist of the index $j$ and also of the $n-1$ indices corresponding to the smallest $x\_i$s. If these $x\_i$s add to at most $(1-c)X$ then this choice of $I$ satisfies the above constraint: the sum $\sum\_{i\in I}x\_i$ is at least $x\_j \ge \frac{X}{3} = \frac{1}{3}X \ge cX$ and at most $(1-c)X$. Thus, this set of indices $I$ can be used to select one of the groups of size $n+1$ in a solution to the packing problem instance. On the other hand, if these $x\_i$s add to more than $(1-c)X$ then the instance cannot be solved: one of the two halves will include $x\_j$ and the sum of that half is always going to be more than $(1-c)X$ (since it was more than that even when we put the smallest elements with $x\_j$).

Thus, we have handled the case that some $x\_j$ has value at least $\frac{X}{3}$. The remaining case is that every $x\_i$ has value at most $\frac{X}{3}$. Then assign the $x\_i$s to two groups, 1 and 2, arbitrarily. Create a matching of the elements of the two groups and swap those pairs one pair at a time. Over the course of this process, the sum of the elements of group 1 will move from it's initial sum to the initial sum of group 2's elements. In other words, the sum of group 1 will cross the average value $\frac{X}{2}$. Each step in this process involves group 1 losing an $x\_i$ and gaining one; since the $x\_i$s have value at most $\frac{X}{3}$, a pair of $x\_i$s differs by at most $\frac{X}{3}$ and so each step moves the sum of group 1 by at most $\frac{X}{3}$. Thus, there will be some point in the process when the sum of group 1 is within half the maximum step size of the average. Thus, at some point the sum of group 1 will fall within $\frac{X}{2} \pm \frac{X}{6}$. But this is the interval $[\frac{1}{3}X, \frac{2}{3}X]$, which is a subinterval of $[cX, (1-c)X]$. Thus, at some point during this process, the group 1 at the time will satisfy our desired condition. We can use this group of $x\_i$s to select a corresponding group of $a\_i$s; these $a\_i$s form one of the two groups of size $n+1$ needed to solve the packing problem instance.

## Conclusion

The above exhaustive casework can be used as an algorithm to partition a list into three groups of the same sum using one soft number. The casework will also identify when this is impossible. The runtime of this algorithm is polynomial.

> **Comments:**
> **username_0**: Thanks!  Lemma 1 proof can be shortened: order group 2's elements by increasing order. Let group 2a be the odd-indexed elements and group 2b the even-indexed elements. Each element in 2a is smaller than the next element which is in 2b, so $S_{2b} \geq S_{2a}$. On the other hand, if we remove the smallest element from 2a and the largest element from 2b, the sum of elements remaining in 2a is at least the sum of elements remaining in 2b. So $S_{2b}-S_{2a}\leq$ the largest minus smallest element = $l/2$. By the assumption, $S_{2b}+S_{2a}\leq 2s-l/2$. Summing the inequalities gives $S_{2b}\leq s$.  
> **username_0**: Question: you mention a sub-problem: "is it possible to partition the $2n+2$ smallest $a_i$-s into two groups of size $n+1$ such that each of those two groups has sum at most $s$?". Why is this problem not as hard as the PARTITION problem?  
> **username_3**: You're right, my Lemma 1 proof is not the simplest possible. I'm a bit too lazy to put in the edits though (especially since other parts of the proof reference the techniques used in the proof). As for the sub-problem, the reason it is not as hard as PARTITION is that you don't actually have to solve that subproblem in full generality: the value of $s$ is not arbitrary. In order to fall into that case, there are specific additional constraints on $s$ and on the $a_i$s that must hold. If these constraints were missing, you would be right: the problem would be as hard as PARTITION.  
> **username_0**: Thanks a lot for the clear and detailed solution.  
> **username_0**: Hi Mikhail, we are working on a paper in which this result is useful. Would you like to join? If so then please write me an email.  

---

### Answer by username_4 on 2019-02-04. Score: 3

**Edit:** The result is incorrect, see the discussion at the end.

Inspired by Mikhail Rudoy's answer, we can generalize to partitioning into $k$ parts with equal sum. The problem is polynomial time solvable for each constant $k$.

The input is $a\_1,\ldots,a\_n$ such that $a\_n$ is the largest number.
Mikhail's observations are, wlog,

* the soft number is $a\_n$
* $a\_i>\frac{a\_n}{k-1}$ for each $i$

wlog, assume that the sum of $a\_1,\ldots,a\_{n-1}$ is $1$ (that is, $1=ks-a\_n$).
Note that $a\_n \geq \frac{1}{n-1}$, so $a\_i > \frac{1}{(k-1)(n-1)}>\frac{1}{kn}$ for each $i$. The problem is equivalent to partitioning the numbers $a\_1,\ldots,a\_{n-1}$ into $k$ subsets such that the sum of each subset is at most $s := \frac{1+a\_n}{k}$.

We consider a restriction of the [multiple knapsack problem](https://en.wikipedia.org/wiki/Multiple_knapsack_problem).
Define the *$k$-knapsack problem* as an instance of the multiple knapsack problem with $k$ knapsacks of the same capacity, where the value of each item equals the weight of the item.

Let the input for the $k$-knapsack problem be $a\_1,\ldots,a\_{n-1}$, and each knapsack has capacity $s$. The following claim is clear.

*Claim*: A $(1-\frac{1}{kn})$-approximation algorithm for the $k$-knapsack problem returns $1$, if and only if all the numbers $a\_1,\ldots,a\_{n-1}$ can be packed into the $k$ knapsacks.

By the above claim, we just have to find a $(1-\frac{1}{kn})$-approximation algorithm for the $k$-knapsack problem.

*Claim*: There is a pseudopolynomial time algorithm for knapsack generalizes for $k$-knapsack for each constant $k$.

*Proof*: Define $D[b\_1,\ldots,b\_k,i]$ to be the maximum value using elements $a\_1,\ldots,a\_i$, where the knapsack has capacity $b\_1,\ldots,b\_k$. The recurrence relation is $D[b\_1,\ldots,b\_k,i+1] = \max( \max\_{j} (D[b\_1,\ldots,b\_j-a\_{i+1},b\_k,i])+a\_{i+1},D[b\_1,\ldots,b\_k,i])$. The base case are simple.
The running times is $O(s^kkn)$.

~~It is standard to obtain an FPTAS by scaling all numbers and round to integers, [see section 5 of this](http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf). This means we can find a $(1-\frac{1}{kn})$-approximation to $k$-knapsack problem in polynomial time.
Therefore for each constant $k$, the original problem can be decided in polynomial time.~~

The above is incorrect, due to the pseudopolynomial time algorithm does not transform into an FPTAS. However, the approach might still give us some insight because we have a very special case of $k$-knapsack problem.

> **Comments:**
> **username_0**: I found this paper: https://epubs.siam.org/doi/abs/10.1137/S0097539700382820 which shows a PTAS for multple-knapsack. How do you obtain an FPTAS from it? (did you mean that there is an FPTAS for the special case in which the values are equal to the weights?)  
> **username_4**: I have made an update. The FPTAS is for the case when $k$ is a constant. If the number of knapsacks is part of the input, there is no FPTAS.  
> **username_0**: Hi Chao, we are working on a paper in which this result is useful. Would you like to join? If so then please write me an email.  

---

### Answer by username_2 on 2019-01-27. Score: 3

This answer does **not** solve the question.
It only settles the following auxiliary problem formulated by @JohnDvorak in the comments (partitioning a set in 1:2 ratio):

> **Auxiliary problem:**  
> **Instance:** Positive rationals $a\_1,\ldots,a\_m$ with $\sum\_{i=1}^m a\_i = 3A$.  
> **Question:** Does there exist an index set $I\subseteq\{1,\ldots,n\}$ with $\sum\_{i\in I}a\_i=A$?

* Take an instance of classical PARTITION (rationals $b\_1,\ldots,b\_n$ with sum $2B$, can you split them into two groups with sum $B$).
* Take $b\_1,\ldots,b\_n$ together with the four numbers $5B,5B,5B,7B$ to create an instance of the auxiliary problem. The sum of all $n+4$ numbers then is $24B$, so that $A=8B$.
* Splitting the $n+4$ numbers into a group with sum $A=8B$ and a group with sum $2A=16B$ is possible if and only if the PARTITION instance has answer YES.

Hence @JohnDvorak's auxiliary problem is NP-complete

> **Comments:**
> **username_0**: Hi Gamow, we are working on a paper in which this result may be useful. Would you like to join? If so then please write me an email.  

---

