Efficient algorithm for 'unsumming' a set of sums

Question

Given a multiset of natural numbers X, consider the set of all possible sums:

$$\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\}$$

For example, $\textrm{sums}(\left\{1,5\right\}) = \left\{0, 1, 5, 6\right\}$ while $\textrm{sums}(\left\{1,1\right\}) = \left\{0, 1, 2\right\}$.

What is the most efficient algorithm for calculating the inverse operation (measured in terms of the size of the input set of sums)? Specifically is it possible to efficiently calculate any of the following:

1. Whether a given set is a valid set of sums. (For example, $\left\{0,1,2\right\}$ is valid but $\left\{0,1,3\right\}$ is not.)
2. A multiset that sums to the given set.
3. The smallest multiset that sums to the given set. (For example, $\left\{1,2\right\}$ and $\left\{1,1,1\right\}$ both sum to $\left\{0,1,2,3\right\}$ but the former is smaller.)

Answer 1

Solution

Solution has two parts. First we discover minimal set, then we prove that it can represent the power sum set. The solution is adjusted for programming implementation.

Minimal set algorithm

1. Find maximal element $a_{m}$ from the sum (multi)set. $P$, the potential minimal (multi)set is initially empty.

2. Unless there is only one group, represent $a_{m}$ in all possible ways as a pair of sums that add up to $a_{m}$, $S_{ij}=\{(a_{i},a_{j})|a_{i}+a_{j}=a_{m}\}$

3. Check that all elements from the set of sums are included.

4. Find maximal element $a_{s}$ from all $S_{ij}$ (meaning together) with the following property: for each $S_{ij}$, $a_{s}$ is either in $S_{ij}$, or we can find $a_{p}$ from the set of sums so that $a_{p}+a_{s}$ is in $S_{ij}$.

5. If it is the case that $S_{ij}$ does not contain $a_{s}$, just the sum $a_{s}+a_{p}$, remove $a_{p}+a_{s}$ from $S_{ij}$ (or just set a mark to ignore it) and insert $a_{p}$ and $a_{s}$ in $S_{ij}$ instead.

6. If an element is present in every $S_{ij}$ remove it from all $S_{ij}$ once (or just set a mark to ignore it and not to touch it any longer) and add it to the list of elements of potential minimal set $P$.

7. Repeat until all $S_{ij}$ are empty

8. If some of $S_{ij}$ remains non-empty and we cannot continue, try again with the maximum value from all $S_{ij}$.

9. Recreate the recursive steps without removals and continue with power set coverage algorithm over $P$. (Before this, you can make a safe-check that $P$ includes all elements that cannot be represented as a sum of two elements so they must be in underlying set for sure. For example, the minimal element must be in $P$.)

(10. Observe that a minimal set solution which is the goal of the algorithm cannot contain more than one repetition of the same number.)

Example:

$$\{2,3,5,7,8,10,12,13,15\}$$

Represent 15 in all possible ways as a sum of two numbers from the set of sums.

$$(13,2),(12,3),(10,5),(8,7)$$

Try to find maximal number that is in all groups or that can be represented as a sum. Obviously we can start searching for it from 8, there is no point going above it.

13 from the first group is 13=8+5 so 13 is fine, but 12 from the second group is not fine since there is no 4 to make 12=8+4 in the set of sums. Next we try with 7. But immediately 13 cannot be covered, there is no 6.

Next we try 5. 13=5+8, 12=5+7, 10=5+5, and for the last either 8=5+3 or 7=5+2 but not both. The groups are now:

$$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$

5 is repeating in all groups so we extract it $P=\{5\}$. We extract 5 only once from each group.

$$(8,2),(7,3),(5,5),(3,7)$$

Obviously there is no point going higher than 5 so we try 5 again. 8=5+3, 7=5+2, so all is fine

$$((5,3),2),((5,2),3),(5,5),(3,(5,2))$$

Extract one 5 again from all groups since it is repeating. (This is not common but our case is deliberately created to display what to do in case we have repetitions.) $P=\{5,5\}$

$$(3,2),(2,3),(5),(3,2)$$

Now we try with 3 and have 5=3+2. Add it to the group.

$$(3,2),(2,3),(3,2),(3,2)$$

Now extract 3 and 2 since they are repeating everywhere and we are fine $P=\{5,5,3,2\}$ and the groups are empty.

$$(),(),(),()$$

Now, we need to recreate recursive steps without removals, this simply means doing the above without really removing the elements from $S_{ij}$ just placing them in $P$ and marking not to alter it any longer.

$$(13,2),(12,3),(10,5),(8,7)$$ $$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$ $$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$

Power set coverage

The purpose of this part is to check if the found minimal set is able to cover the power sum set. It is possible that a found solution can cover all given sums, but that they are not power set sums. (Technically, you could simply create a power sum set from the found minimal set and check if each sum, as power set dictates, is in the initial sum set. This is all that just merged with what we already have, so nothing is wasted. You can do this part while rewinding the recursion.)

1. Encode all elements from the minimal set using successive powers of 2. The order is not important. Encode the same element with a new value as many times as it is repeating. Start from C=1, every next element has C=2C.

$$(2=[1],3=[2],5=[4],5=[8])$$

2. Replace the elements in the restored recursion list,

$$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$

with the encoding: 2 with 1, 3 with 2, 5 with 4, and another 5 with 8. Observe that each element has different encoding even though they are repeated.

$$((4,(8,2)),1),((4,(8,1)),2),((4,(2,1)),8),((8,2),(4,1))$$

3. Collect all intermediate sums, at the moment we have (1,2,4,8)

$$((4,(10)),1),((4,(9)),2),((4,(3)),8),((10),(5))$$

Intermediate sums $(1,2,3,4,5,8,9,10)$

$$((14),1),((13),2),((7),8),(15)$$

Intermediate sums $(1,2,3,4,5,8,9,10,13,14,15)$

$$\{(15),(15),(15),(15)\}$$

4. Check that the result is $2^m-1$, where $m$ is the number of elements in the solution, in the example $m=4$

5. Collect missing numbers from $1$ to $2^m-1$ in the intermediate sum list

$(6,7,11,12)$

6. Justify their absence in the following manner: represent each number in binary form

$(6=0110_2)$ $(7=0111_2)$ $(11=1011_2)$ $(12=1010_2)$

$6$ represents the sum of 3+5 since $0110_2$ is covering second and third element from $(2=[1],3=[2],5=[4],5=[8])$. The sum of these elements, 8, is listed in the initial sum list $\{2,3,5,7,8,10,12,13,15\}$, so all is fine.

$7$ represents the sum of 2+3+5 since $0111_2$ is covering first three elements from $(2=[1],3=[2],5=[4],5=[8])$. The sum of these elements, 10, is listed in the initial sum list so all is fine.

$11$ is 2+3+5, and 10 is in the list. $12$ is 3+5, and 8 is in the list.

If any binary representation corresponds to the sum that cannot be found, report that there is no solution.

So all is fine and $(2,3,5,5)$ is the solution. It is the minimal solution as well.

Discussion

It was necessary to provide the algorithm that is going to check if the sums cover the power set completion, which is what is hidden in the binary expansion. For example if we exclude 8 and 7 from the initial example, the first part would still provide the solution, only the second part would report missing combinations of sums.

First part of discovering the possible minimal set is $mnlog(m)$ which comes to $m\log^2(m)$: we are looking around $m$ elements $n$ times having one $\log(m)$ binary search.

The last part is done in recursion return and it does not require any special effort, we are searching over less than $m$ elements, we need binary form which is $\log{m}$ and we have one addition and search if the sum is in the list, so together it is again about $m\log^2(m)$.

If we assume that the number of elements in the power sum set corresponds to the number of partitions of the largest element in the underlying set then the complexity is around $m\log^3(m)$. Any of the two justifies the initial sorting in order to find the largest element.

Parts of the algorithm assume that we can find the pair of sums in linear time and this requires sorting.

Incorrect start

First part of the algorithm may fail, if we have started it on the wrong foot. For example $2,3,4,5,6,7,8,9,10,11,12,13,15$ has the basic solution $2,3,4,6$ which you get if you start algorithm from 6. However we can start our algorithm from 7, since there is nothing in step 4. that would say not to, and lock ourselves in, the algorithm cannot end properly. The reason is that 7 is 7=4+3 and 4 and 3 are in the solution. So locked algorithm does not always mean that there is no solution, just to try again with lower initial value. In that case, some ideas about the possible values are hidden within remaining $S_{ij}$. That is why we suggested starting from there in case of failure.

Another example, if you miss and start algorithm from 5, you would get $5,4,3,3$ but this one does not include 2.

Notice that this algorithm is not going to give a derived solutions like $2,2,3,4,4$, which we got simply by turning 6 into 4 and 2 in the solution $2,3,4,6$. There are special rules that cover these versions.

The purpose of this algorithm is to provide a solution once we have started it all correctly.

Improvements

Step 4. is the one that could be upgraded in this manner: instead of maximal we could try out every element in descending order that satisfies the given condition. We create a separate branch for each. If some branch does not give a solution, cancel it.

For example for $2,3,4,5,6,7,8,9,10,11,12,13,15$ we could try in the first round $7,6,5,4$ in separate ways since all of them are passing the first test. (There is no reason to use 2 or 3 since we know they have to be in the underlying set.) and simply continue that way all around until we collect all versions that can reach the end. This would create a full-coverage solution which would discover more than one underlying set.

Another thing, since we know that we cannot have more than one repetition if the case is minimal, we can incorporate this in our algorithm.

Overall, the condition in step 4. that a number must repeat in every group or have ability to create a sum is strong enough to get us out of direct exponential waters, which would be an algorithm of simply trying out every combination and creating the power set over each until we find a match.

Answer 2

NOTE: This does not quite work in general, see Uri's counterexample below.

One way of achieving at least 1. and 2. for a given set $Y$ (minimality requires a bit of tweaking) is (sorting $Y$ first, if necessary):

• Check whether $0\in Y$. If not, there is no solution.
• Let $y$ be the smallest positive number in $Y$. Then $y$ must also be in $X$, if it exists (otherwise it would be the sum of smaller positive numbers, which would also occur in $Y$).
• Let $z_1<\dots<z_n$ be the remaining members of $Y$. We will try to find a set $Y'$ such that $Y = Y' + \{0,y\}$. Obviously $0$ must be in $Y'$. For $i=1,\dots,n$: if $z_i+y\in Y$, add $z_i$ to $Y'$; otherwise, if $z_i-y\notin Y$, there is no solution; otherwise (i.e. if $z_i+y\notin Y$, but $z_i+y\in Y$), we don't need $z_i$ in $Y'$.
• Repeat recursively with $Y'$, collecting the minimal elements $y,y',\dots$ into a multiset. This is your solution iff you end up with an empty set.}

In each recursive step, the size of the set decreases by at least $1$ (since we exclude the least element $y$), so the number of steps is in $O(n)$. Each step contains a single iteration over the current set, for an $O(n^2)$ total complexity (assuming unit costs for arithmetic operations).

Finding a minimal solution (note that this is not necessarily unique; for example, for $Y=\{0,1,3,4,5,6,7\}$ we have $\{0,1,3,4,6\}$ and $\{0,1,3,5,6\}$) is slightly more involved: after finding the minimum $y\in Y$, you would analyze the arithmetic progressions $\{a+k\cdot y\}$ in $Y$, reject if one of them is a singleton, and otherwise pick alternating members for $Y'$; if a progression has odd length, you need to pick some pair of successive members, hence the non-uniqueness.