Найти подмножество N чисел в массиве, сумма которых равна 0 [Задача суммы подмножеств, которая возвращает подмножество] - PullRequest
Новая
       25

Найти подмножество N чисел в массиве, сумма которых равна 0 [Задача суммы подмножеств, которая возвращает подмножество]

1 голос
/ 31 мая 2011

Я пытаюсь попрактиковаться в вопросе интервью в заголовке

Для тех, кто непосредственно хочет знать мой вопрос, перейдите к «Меньшая версия моего вопроса» .

Для получения дополнительной информации читайте дальше.

=> Для N = 2, Мы можем просто использовать карту.

=> Для N = 3, существует n ^ 2 решение: Нахождение трех элементов в массиве, сумма которых ближе всего к данному числу [Проверьте принятый ответ, он фактически даст вам решение на сумму до 0, а не до как в заголовке ссылки]

Я думаю, используя приведенную выше ссылку, мы можем иметь 3 указателя для N = 4 и получить решение n ^ 3.

В любом случае, я хочу подчеркнуть, что в конечном итоге все эти решения не будут масштабироваться с ростом N. Поэтому я ищу решение общего назначения

Я думаю, что это может быть выведено из задачи о подмножестве сумм Проблема подмножества сумм . Однако решение [динамическая версия программирования] этой проблемы возвращает логическое значение. Я ищу фактическое подмножество.
Само логическое решение не совсем естественно для получения [в том смысле, что вы не можете «получить» ответ легко, если вы не прочитали его… Мне пришлось написать пример, чтобы понять его]. В любом случае, я ищу способ изменить его, чтобы дать мне подмножество, а не просто логическое значение.

Меньшая версия моего Вопроса:
Измените это, чтобы вернуть фактическое подмножество, а не просто логическое значение 

Let S[i] = true if we can make sum i and false otherwise.

S[0] = true // we can always make sum 0: just don't choose any number
S[i] = false for all i != 0
for each number i in your input
    for s = MaxSum downto i
        if ( S[s - i] == true )
            S[s] = true; // if we can make the sum s - i, we can also make the sum s by adding i to the sum s - i.

1 Ответ

1 голос
/ 31 мая 2011

Просто сделайте S[s] содержит список чисел, которые составляют эту сумму, когда это возможно: 

Let S[i] = the list of numbers that make up that sum and false (or null, something distinct from an empty list) otherwise.

S[0] = empty list // we can always make sum 0: just don't choose any number
S[i] = null for all i != 0
for each number i in your input
    for s = MaxSum downto i
        if ( S[s - i] != null )
            S[s] = S[s-i] with i added; // if we can make the sum s - i, we can also make the sum s by adding i to the sum s - i.
...