Как решить проблему суммы подмножеств с массивом размера sum + 1

Question

Поскольку проблема не нова и существует множество алгоритмов, которые ее решают, я предположил, что вопрос может дублироваться, но я не нашел ни одного.

Существует набор элементов.Задача состоит в том, чтобы найти подмножество с суммой, равной некоторой s переменной.

Примитивное решение является простым и может быть решено за экспоненциальное время.В рекурсивном подходе DP предлагается добавить памятку, чтобы уменьшить сложность или работать с двумерным массивом (снизу вверх).

Я нашел еще один в комментарии к geeksforgeeks, но не могу понять, как он работает.

def is_subset_sum(a, s):
    n = len(a)
    res = [False] * (s + 1)
    res[0] = True
    for j in range(n):
        i = s
        while i >= a[j]:
            res[i] = res[i] or res[i - a[j]]
            i -= 1
    return(res[s])

Может кто-нибудь объяснить алгоритм?Что элементы массива на самом деле имеют в виду?Я пытаюсь отследить это, но не могу с этим справиться

Answer 1

Ввод слов в код: пробуя каждый элемент в списке по очереди, установите временную переменную i в целевую сумму. Хотя i не меньше, чем текущий элемент, a[j], сумма, равная текущему значению i, либо (1) уже достижима и помечена так, либо (2) достижима путем добавления текущего элемента, a[j], к сумме, равной вычитанию текущего элемента из текущего значения i, которое мы, возможно, уже отметили. Таким образом, мы перечисляем все возможности в O(s * n) времени и O(s) пространстве. (i может быть плохим выбором для этого имени переменной, поскольку его, скорее всего, чаще всего представляют индексом, а не суммой. Хотя в этом случае проверяемые суммы сами также являются индексами.)