Недавно я столкнулся с этим вопросом в конкурсе найма:
Дан массив S из 2^N целых чисел (1 ‹= N ‹= 20, 0 ‹= Si ‹= 10^9), представляющий суммы подмножеств массива A, нам нужно восстановить массив A в отсортированном порядке.
например S = {2, 1, 0, 3} => A = {1, 2}, поскольку суммы подмножеств A равны {0, 1, 2, 1+2}
Порядок чисел в массиве S может быть случайным.
Как я могу подойти к этой проблеме? Заранее спасибо.
Вы можете отсортировать массив, содержащий суммы подмножества. Когда вы сортируете массив сумм подмножества, Ai = S[2^i] -- должен дать вам значения массива A в отсортированный порядок.
Вы можете составить таблицу истинности, чтобы получить сумму подмножества и проследить обратно Предполагая, что S является допустимым вводом, например: S = {0, 5, 3, 8, 1, 6, 4, 9}
Sorted S = {0, 1, 3, 4, 5, 6, 8, 9}
A = [A0, A1, A2] ---
A0,A1,A2 -- (Binary, part of subset = 1 not part = 0 )
Index | A0,A1,A2 | Sorted Sum
0 0 0 0 0
1 1 0 0 1
2 0 1 0 3
3 1 1 0 4
4 0 0 1 5
5 1 0 1 6
6 0 1 1 8
7 1 1 1 9
From her we can reverse and find that A0 = S[2^0], A1 = S[2^1], A2 = S[2^2]
