Восстановить исходный массив из всех подмножеств

Question

Вам даны все суммы подмножеств массива.Затем вы должны восстановить исходный массив из предоставленных сумм подмножеств.

Каждый элемент в исходном массиве гарантированно будет неотрицательным и меньше 10 ^ 5.В исходном массиве не более 20 элементов.Исходный массив также отсортирован.Вклад гарантированно будет действительным.

Пример 1

Если предоставлены следующие подмножества:

0 1 5 6 6 7 11 12

Мы можем быстро сделать вывод, что размер исходного массива равен 3так как есть 8 (2 ^ 3) подмножеств.Выход (то есть исходный массив) для вышеуказанного ввода выглядит так:

1 5 6

Пример 2

Вход:

0 1 1 2 8 9 9 10

Выход:

1 1 8

Что я пробовал

Поскольку все элементы гарантированно неотрицательны, наибольшее целое число на входе должно быть суммой массива.Однако я не уверен, как мне поступить оттуда.По логике я подумал, что следующие (2 ^ 2 - 1) самые большие суммы подмножеств должны включать все, кроме одного элемента из массива.

Однако приведенная выше логика не работает, если исходный массив такой:

1 1 8

Вот почему я застрял и не уверен, что делать дальше.

Answer 1

Вот простой алгоритм, который не требует поиска суммы подмножеств для данного числа.

S ← входная последовательность
X ← пустая последовательность

В то время как S не имеетнулевой элемент:

1. d ← второй наименьший элемент S (наименьший всегда равен нулю)
2. Вставить d в X
3. N ← пустая последовательность
4. Пока S не пусто:
   • z ← наименьший элемент из S
   • Удалить z и z + d из S (если S не содержит z + d, это ошибка;удалить только один экземпляр z и z + d, если их несколько).
   • Вставить z в N.
5. S ← N

Выход X.

Answer 2

Say S - это массив подмножеств, а A - исходный массив.Я предполагаю, что S отсортировано.

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

В общем, S [i] для i> = 3 - это либо элемент A, либо комбинация элементов A, с которыми вы уже сталкивались.При обработке S пропустите один раз для комбинации известных элементов A, которые генерируют данное число, добавьте все оставшиеся числа к A. Остановитесь, когда A достигнет нужного размера.

Например, если A = [1,2, 7,8,9], тогда S будет включать [1,2,1 + 2 = 3, ..., 1 + 8 = 9, 2 + 7 = 9,9, ...].При обработке S мы пропускаем две 9 из-за 1 + 8 и 2 + 7, затем видим третий 9, который, как мы знаем, должен принадлежать A.

Например, если S = ​​[0,1,1,2, 8,9,9,10] тогда мы знаем, что у A есть 3 элемента, что первые 2 элемента A равны [1,1], когда мы добираемся до 2, мы пропускаем его, потому что 1 + 1 = 2, мы добавляем 8 имы закончили, потому что у нас есть 3 элемента.