Алгоритм поиска множества, когда задан набор сумм подмножеств набора мощности

Question

Из набора A из N положительных чисел , набор из Sum из всех возможных подмножеств из набора A и учитывая . Мы должны найти набор A.

Мой подход состоит в том, чтобы сначала отсортировать, а затем отбирать наибольшее число Nth из наибольшего числа, чтобы найти элементы набора. Что не так с таким подходом?

Answer 1

Рассмотрим набор элементов как {a,b,c,d}, в таком случае возможные суммы подмножеств набора будут (1) {a}, (2) { b + c}, (3) {b + c + d}, (4) {a + b + c + d} и другие. Однако наибольшая сумма подмножества будет (4), и, как видно, вычитание (4) - (2) даст {a+d}, что является просто еще одной суммой подмножества набора, а не фактическим элементом.

Возможный способ решить проблему - отсортировать массив и начать собирать элементы из самых маленьких в мешке. Каждый раз, когда мы выбираем новый элемент, мы вычисляем все возможные суммы подмножеств, которые всегда включают этот элемент и другие элементы из нашего поддерживаемого пакета, а затем удаляем эти вычисленные суммы поднаборов из данного списка сумм подмножеств. Затем мы переходим к поиску следующего наименьшего элемента из данного списка подмножеств, который еще не был удален.

РЕДАКТИРОВАТЬ: Добавлено возможное решение данного вопроса.