Recover original array from all subsets

Question

You are given all subset sums of an array. You are then supposed to recover the original array from the subset sums provided.

Every element in the original array is guaranteed to be non-negative and less than 10^5. There are no more than 20 elements in the original array. The original array is also sorted. The input is guaranteed to be valid.

Example 1

If the subset sums provided are this:

0 1 5 6 6 7 11 12

We can quickly deduce that the size of the original array is 3 since there are 8 (2^3) subsets. The output (i.e original array) for the above input is this:

1 5 6

Example 2

Input:

0 1 1 2 8 9 9 10

Output:

1 1 8

What I Tried

Since all elements are guaranteed to be non-negative, the largest integer in the input must be the total of the array. However, I am not sure as to how do I proceed from there. By logic, I thought that the next (2^2 - 1) largest subset sums must include all except one element from the array.

However, the above logic does not work when the original array is this:

1 1 8

That's why I am stuck and am not sure on how to proceed on.

Answer 1

I revisited this question a few years later and finally managed to solve it! The approach that I've used to tackle this problem is the same as what Dave had devised earlier. Dave gave a pretty concrete explanation so I'll just add on some details and append my commented C++ code so that it's a bit more clear;

Excluding the empty set, the two smallest elements in S has to be the two smallest elements in A. This is because every element is guaranteed to be non-negative. Having known the values of A[0] and A[1], we have something tangible to work and build bottom-up with.

Following which, any new element in S can either be a summation of the previous elements we have confirmed to be in A or it can an entirely new element in A. (i.e S[3] = A[0] + A[1] or S[3] = A[2]) To keep track of this, we can use a frequency table such as an unordered_map<int, int> in C++. We then repeat this process for S[4], S[5]... to continue filling up A.

To prune our search space, we can stop the moment the size of A corresponds with the size of S. (i.e |A| = log(|S|)/log2). This help us drastically cut unnecessary computation and runtime.

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

int main () {
    int n; cin>>n;
    vi S, A, sums;
    unordered_map<int, int> freq;
    for (int i=0;i<(int) pow(2.0, n);i++) {
        int a; cin>>a;
        S.push_back(a);
    }
    
    sort(S.begin(), S.end());

    // edge cases
    A.push_back(S[1]);
    if (n == 1) {for (auto v : A) cout << v << "\n"; return 0;}
    A.push_back(S[2]);
    if (n == 2) {for (auto v : A) cout << v << "\n"; return 0;}
    
    sums.push_back(0); sums.push_back(S[1]); sums.push_back(S[2]);
    sums.push_back(S[1] + S[2]);
    
    freq[S[1] + S[2]]++; // IMPT: we only need frequency of composite elements

    for (int i=3; i < S.size(); i++) {
        if (A.size() == n) break; // IMPT: prune the search space
        
        // has to be a new element in A
        if (freq[S[i]] == 0) {
            // compute the new subset sums with the addition of a new element
            vi newsums = sums;
            for (int j=0;j<sums.size();j++) {
                int y = sums[j] + S[i];
                newsums.push_back(y);
                if (j != 0) freq[y]++; // IMPT: coz we only need frequency of composite elements
            }
            // update A and subset sums
            sums = newsums;
            A.push_back(S[i]);
        } else {
            // has to be a summation of the previous elements in A
            freq[S[i]]--;
        }
    }

    for (auto v : A) cout << v << "\n";
}

Answer 2

Here's an easy algorithm that doesn't require finding which subset sums to a given number.

S ← input sequence
X ← empty sequence

While S has a non-zero element:

1. d ← second smallest element of S (the smallest one is always zero)
2. Insert d in X
3. N ← empty sequence
4. While S is not empty:
   • z ← smallest element of S
   • Remove both z and z+d from S (if S does not contain z+d, it's an error; remove only one instance of both z and z+d if there are several).
   • Insert z in N.
5. S ← N

Output X.

Answer 3

Say S is the subset sum array and A is the original array. I'm assuming S is sorted.

|A| = log2(|S|)
S[0] = 0
S[1] = A[0]
S[2] = A[1]
S[3] = EITHER A[2] OR A[0] + A[1].

In general, S[i] for i >= 3 is either an element of A or a combination of the elements of A that you've already encountered. When processing S, skip once per combination of known elements of A that generate a given number, add any remaining numbers to A. Stop when A gets to the right size.

E.g., if A=[1,2,7,8,9] then S will include [1,2,1+2=3,...,1+8=9, 2+7=9,9,...]. When processing S we skip over two 9s because of 1+8 and 2+7, then see a third 9 which we know must belong to A.

E.g., if S=[0,1,1,2,8,9,9,10] then we know A has 3 elements, that the first 2 elements of A are [1,1], when we get to 2 we skip it because 1+1=2, we append 8 and we're done because we have 3 elements.