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.
