Subset Sum Problem

Q: Как найти значения, которые дают целевое значение?

Сохраните всю таблицу и начните с made[n][target] . Поднимайтесь на одну строку за раз: если made[i-1][s] имеет значение true, nums[i-1] не понадобилось; в противном случае запишите его и вычтите из s . Остановитесь, когда сумма станет равна 0 и будет найден один допустимый элемент.

СреднеДинамическое программирование

+10

nums содержит положительные целые числа, а target — положительное целое число. Можешь выбрать некоторые значения, используя каждую позицию не более одного раза, так, чтобы их сумма точно равнялась target? Возвращай true, если это возможно, и false, если подходящего набора нет.

Функция

isSubsetSum(nums: integer-array, target: integer) → boolean

numsinteger-array: положительные значения, которые вы можете выбрать
targetinteger: точная сумма, которой должны достичь выбранные значения
Возвращаетboolean: true, если сумма некоторых значений в точности равна target, иначе false

Ограничения

1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 10⁴
1 ≤ target ≤ 10⁴

Примеры

Ввод: nums = [8, 3, 11, 5, 7]target = 15
Вывод: true
Пояснение: 8 + 7 = 15, поэтому ответ — true. Вариант 3 + 5 + 7 тоже подходит; достаточно одного варианта.

Ввод: nums = [6, 9, 12, 15]target = 20
Вывод: false
Пояснение: Каждое значение кратно 3, поэтому и любая их сумма также кратна 3. 20 не кратно 3, поэтому ответ — false.

Ввод: nums = [4, 1, 2]target = 8
Вывод: false
Пояснение: Все три значения вместе дают 4 + 1 + 2 = 7, что меньше 8, поэтому никакой выбор не может достичь этого значения, и ответ — false.

Дополнительный вопрос

Два одинаковых значения на разных позициях считаются разными вариантами выбора. Сколько вариантов выбора в сумме дают target?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Для каждого значения есть выбор «взять или не взять», поэтому для 200 значений получается 2^200 вариантов. Однако имеют значение только суммы до target ≤ 10^4. Записывай, какие суммы можно получить из уже обработанных значений: каждое новое значение сдвигает эту запись на свою величину, и поиск превращается в таблицу из n × target логических значений.

Возьмите или пропустите каждое значение

Верно, но не успевает на самых больших тестах

Идея

canMake(i, remaining) проверяет, можно ли получить ровно remaining, используя значения начиная с позиции i. Выбери nums[i], если оно подходит: тогда для остальных останется remaining-nums[i]; если не получится, пропусти его. Каждый выбор — это один путь, поэтому поиск находит подходящий выбор, если такой существует.

Если подходящего выбора нет, поиск проходит все варианты. При 200 числах, кратных 3, каждое из которых не больше 300, и цели 9998 ни один выбор не подходит, но любые 33 значения в сумме меньше цели: это больше 10^37 путей.

Алгоритм

Напиши canMake(i, remaining).
Значение remaining, равное 0, означает, что выбор завершён: верни true. Если значения закончились, а нужное значение ещё не получено, верни false.
Если nums[i] ≤ remaining и canMake(i+1, remaining-nums[i]) равно true, верни true.
В противном случае верни canMake(i+1, remaining).
Верни canMake(0, target).

def isSubsetSum(nums, target):
    n = len(nums)

    # Can some of nums[i], nums[i+1], ... add up to exactly remaining?
    def can_make(i, remaining):
        if remaining == 0:
            return True
        if i == n:
            return False
        if nums[i] <= remaining and can_make(i + 1, remaining - nums[i]):
            return True  # take nums[i]
        return can_make(i + 1, remaining)  # skip it

    return can_make(0, target)

Заполните таблицу достижимых сумм

Идея

Рекурсия зависит только от позиции и оставшейся суммы от 0 до target, и многие пути приводят к одной и той же паре. Вместо этого заполните таблицу. made[i][s] равно true, когда выбор из первых i значений даёт в сумме ровно s; пустой выбор даёт 0. При num = nums[i-1] сумма s достижима, если она была достижима без num, made[i-1][s], или если num дополняет s-num, made[i-1][s-num], при s ≥ num.

В первом примере после 8 достижимые суммы — 0 и 8. Число 3 добавляет 3 и 11, число 11 добавляет только 14, число 5 добавляет 5 и 13, а 8 + 7 даёт 15. При максимальных ограничениях таблица содержит 201 × 10001 ячеек, то есть около 2 × 10^6 шагов.

Алгоритм

Выдели память для made как для массива из n+1 строк и target+1 логических значений, все — false. Установи made[0][0] в true для пустого набора.
Строка i обрабатывает значение num = nums[i-1] для i от 1 до n.
Для каждой суммы s от 0 до target установи made[i][s] в значение made[i-1][s].
Если s ≥ num и made[i-1][s-num] равно true, установи made[i][s] в true.
Верни made[n][target].

def isSubsetSum(nums, target):
    n = len(nums)
    # made[i][s]: some of the first i values add up to exactly s
    made = [[False] * (target + 1) for _ in range(n + 1)]
    made[0][0] = True
    for i in range(1, n + 1):
        num = nums[i - 1]
        for s in range(target + 1):
            # leave num out, or put it in on top of a sum of s-num
            made[i][s] = made[i - 1][s] or (s >= num and made[i - 1][s - num])
    return made[n][target]

Одна строка сумм, обновляемая сверху

Идея

Каждая строка считывает только строку перед ней, поэтому для неё достаточно одного массива made[s]. Если перезаписывать его сверху вниз, значение будет учитывать само себя: при nums = [5] и целевом значении 10 s = 5 становится истинным, а затем s = 10 считывает эту новую запись, используя 5 дважды.

Вместо этого проходи от target вниз до num. При чтении s-num обращение приходится на ячейку с меньшим индексом, которую проход ещё не перезаписал, поэтому там остаётся строка, существовавшая до обработки num. Если сумма достижима, она останется достижимой, поэтому можно остановиться, как только made[target] станет истинным. Памяти потребуется всего target + 1 логических значений.

Алгоритм

Начни с одного массива из target + 1 логических значений, в котором истинно только made[0].
Бери значения по порядку. Для каждого num перебирай s в обратном порядке: от target до num.
Если made[s-num] истинно, пометь made[s].
Как только made[target] будет помечено, остановись и верни true.
Если сначала будут использованы все значения, ответ — false.

def isSubsetSum(nums, target):
    # made[s]: some of the values seen so far add up to exactly s
    made = [False] * (target + 1)
    made[0] = True
    for num in nums:
        # Downward, so made[s - num] still ignores num
        for s in range(target, num - 1, -1):
            if made[s - num]:
                made[s] = True
        if made[target]:
            return True
    return False

Ловушки и крайние случаи

Цикл вверх по суммам использует одно и то же значение дважды: [3] при целевой сумме 9 возвращает true.
Если забыть про made[0] = true. Каждая сумма строится на пустом выборе, поэтому каждый ответ будет false.
Сначала выбирать наибольшие значения. Для [6, 5, 5] при целевой сумме 10 выбор 6 оставляет 4, которое ничем не получить, тогда как 5 + 5 = 10.
Значение больше target, как в [10000] при целевой сумме 1, не должно ничего менять. num...target в Swift останавливает программу, а (num+1):(target+1) в R отсчитывает в обратном направлении, поэтому сначала проверьте num ≤ target.
В Lua и R запись для суммы s находится по индексу s + 1.

Частые вопросы4

Какова временная сложность задачи о сумме подмножеств?

Таблица требует времени O(n × target), около 2 × 10^6 шагов для 200 значений и target, равного 10^4, а один ряд сокращает расход памяти до O(target). Стоимость зависит от численного размера target, поэтому метод является псевдополиномиальным и бесполезен для такого target, как 10^18. В общем случае задача о сумме подмножеств является NP-полной.

Как задача о сумме подмножества связана с задачей о разбиении на подмножества с равной суммой и задачей о рюкзаке 0/1?

Разбиение на равные суммы подмножеств — это задача о сумме подмножества с target = total / 2 после проверки, что общая сумма чётная. Задача о сумме подмножества — это задача о рюкзаке 0/1, где каждое значение является собственным весом, а рюкзак должен быть заполнен точно, поэтому таблица содержит логические значения вместо лучших значений.

Работает ли задача о сумме подмножества с отрицательными числами?

Идея работает, приведённый выше код — нет. При наличии отрицательных чисел достижимые суммы лежат в диапазоне от суммы отрицательных чисел до суммы положительных, поэтому сдвинь каждый индекс на эту наименьшую сумму и заполни строку тем же способом. Значение, превышающее оставшуюся сумму, больше нельзя пропустить.

Как найти значения, которые дают целевое значение?

Сохраните всю таблицу и начните с made[n][target]. Поднимайтесь на одну строку за раз: если made[i-1][s] имеет значение true, nums[i-1] не понадобилось; в противном случае запишите его и вычтите из s. Остановитесь, когда сумма станет равна 0 и будет найден один допустимый элемент.

def isSubsetSum(nums, target):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

nums = [8, 3, 11, 5, 7]
target = 15

Ожидаемый вывод

true

Subset Sum Problem

Функция

Ограничения

Примеры

Подсказки

Решение

Возьмите или пропустите каждое значение

Заполните таблицу достижимых сумм

Одна строка сумм, обновляемая сверху

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи