Target Sum
Дан массив nums неотрицательных целых чисел и целое число target. Поставьте перед каждым числом знак плюс или минус, сохраните их порядок и вычислите выражение. Верните количество вариантов расстановки знаков, при которых выражение равно target. Каждый из 2^n вариантов считается отдельно, поэтому +0 и -0 — это два разных варианта.
Функция
- numsinteger-array
- числа, каждое из которых получает знак
- targetinteger
- значение, которому должно быть равно выражение
- Возвращаетinteger
- количество вариантов знака, выражение для которых равно целевому значению
Ограничения
1 ≤ nums.length ≤ 200 ≤ nums[i] ≤ 1000- Сумма
numsне превышает 1000. -1000 ≤ target ≤ 1000- Ответ не превышает 220 и укладывается в диапазон 32-разрядного знакового целого числа.
Примеры
- Ввод
- nums = [2, 1, 1]target = 2
- Вывод
- 2
- Пояснение
+2 +1 -1и+2 -1 +1в обоих случаях равны 2. Если поставить минус перед 2, максимальное значение, которого можно достичь, — это -2 + 1 + 1 = 0, поэтому никакой другой вариант не подходит.
- Ввод
- nums = [0, 4, 4]target = 0
- Вывод
- 4
- Пояснение
- Две 4 должны иметь противоположные знаки:
+4 -4или-4 +4, и в обоих случаях 0 может иметь любой знак. Получается 2 × 2 = 4 варианта.
- Ввод
- nums = [6, 3]target = 4
- Вывод
- 0
- Пояснение
- Четыре возможных значения: 9, 3, -3 и -9. Изменение знака меняет сумму на удвоенное значение этого числа, поэтому каждый результат нечётный, например 6 + 3 = 9, и чётное целевое значение 4 никогда не будет достигнуто.
Дополнительный вопрос
Можешь ли ты обработать до 40 чисел со значениями до 10^9, если в памяти не помещается массив с индексами по сумме?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Можно попробовать оба знака для каждого числа, что даст
2^nвыражений. Обрати внимание, что многие разные префиксы знаков приводят к одной и той же текущей сумме, и дальше они ведут себя совершенно одинаково.Обозначим через
Pсумму чисел, перед которыми ставят плюс, а черезN— сумму чисел, перед которыми ставят минус. Известно, чтоP - N = targetиP + N = sum(nums). Что это говорит оP?P = (sum + target) / 2, поэтому подсчитайте подмножестваnums, сумма которых равна этому значению. Хранитеways[s]— количество подмножеств, сумма которых равнаs, — и обновляйте его для каждого числа, перебирая значенияsот большего к меньшему. Сразу верните 0, еслиsum + targetнечётно или|target| > sum.
Решение
У каждого числа есть два знака, поэтому существует 2^n выражений. Подсчёт по позиции и текущей сумме объединяет префиксы знаков, которые приводят к одной и той же сумме. Ещё лучше: числа со знаком плюс образуют подмножество с фиксированной суммой, поэтому задача сводится к подсчёту подмножеств с заданной суммой за время O(n × S), где S — сумма nums.
Попробуй оба знака для каждого числа
Верно, но не успевает на самых больших тестах
Идея
Проходи по числам слева направо, поддерживая текущую сумму, и для каждого числа выбирай один из двух вариантов: прибавить его или вычесть. Когда каждому числу будет присвоен знак, добавь 1, если сумма равна target. Каждый выбор знака соответствует ровно одному пути, поэтому сумма подсчётов и будет ответом.
Это один конечный узел на каждый выбор: 2^20 ≈ 10^6 конечных узлов для 20 чисел, а каждое дополнительное число удваивает объём работы.
Алгоритм
- Запишите
count(i, total)— количество способов расставить знаки передnums[i..], если сумма чисел передiуже равнаtotal. - Если
i == n, верните 1, когдаtotal == target, иначе 0. - В противном случае верните
count(i+1, total + nums[i]) + count(i+1, total - nums[i]). - Ответ —
count(0, 0).
def findTargetSumWays(nums, target):
n = len(nums)
def count(i, total):
# Ways to sign nums[i:] so that the whole expression ends at target
if i == n:
return 1 if total == target else 0
return count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
return count(0, 0)Мемоизируйте по позиции и текущей сумме
Идея
count(i, total) зависит только от i и total, а не от знаков, которые дали эту сумму. Для nums = [1, 1, 1, 1] префиксы +1 -1 и -1 +1 оба дают сумму 0 на позиции 2, поэтому дальнейший поиск будет одинаковым. Сохраняйте каждый результат при первом вычислении и используйте его повторно.
Текущая сумма находится в диапазоне от -S до S, поэтому прибавьте к ней S, чтобы использовать её как индекс: memo[i][total + S]. Всего существует не более n × (2S+1) состояний — около 4 × 10^4 для 20 чисел с суммой 1000, каждое требует постоянного объёма работы.
Алгоритм
- Вычислите
S = sum(nums)и создайте мемоизацию размеромn × (2S+1), заполненную значениями -1. - В
count(i, total)верните базовый случай приi == n, как и раньше. - Если
memo[i][total + S]равно -1, заполните его значениемcount(i+1, total + nums[i]) + count(i+1, total - nums[i]). - Верните сохранённое значение и вызовите
count(0, 0).
def findTargetSumWays(nums, target):
n = len(nums)
whole = sum(nums)
# memo[i][total + whole]: ways for nums[i:] from this running total, -1 while unknown
memo = [[-1] * (2 * whole + 1) for _ in range(n)]
def count(i, total):
if i == n:
return 1 if total == target else 0
if memo[i][total + whole] == -1:
memo[i][total + whole] = count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
return memo[i][total + whole]
return count(0, 0)Подсчитайте подмножества, сумма которых равна (S + target) / 2
Идея
Пусть P — сумма чисел со знаком плюс, а N — сумма остальных. Тогда P - N = target и P + N = S, поэтому 2P = S + target. Выбор знаков подходит тогда и только тогда, когда сумма чисел со знаком плюс равна (S + target) / 2, а каждое такое подмножество соответствует одному выбору знаков.
ways[s] считает подмножества уже рассмотренных чисел, сумма которых равна s; изначально ways[0] = 1. Для каждого числа x подмножество с суммой s либо пропускает x, либо добавляет его к подмножеству с суммой s - x. Перебирай s от большего к меньшему, чтобы ways[s - x] всё ещё содержало значение до обработки x и ни одно число не использовалось дважды. Ноль добавляет каждую запись к самой себе, удваивая все количества: это два варианта знака для нуля. Получается n × goal сложений, не более 2 × 10^4.
Алгоритм
- Вычисли
S = sum(nums). Если|target| > SилиS + targetнечётно, верни 0. - Задай
goal = (S + target) / 2, создайwaysизgoal + 1нулей и задайways[0] = 1. - Для каждого
xвnumsперебирайsотgoalдоxв обратном порядке и прибавляйways[s - x]кways[s]. - Верни
ways[goal].
def findTargetSumWays(nums, target):
whole = sum(nums)
# plus - minus = target and plus + minus = whole, so plus = (whole + target) / 2
if abs(target) > whole or (whole + target) % 2 == 1:
return 0
goal = (whole + target) // 2
# ways[s]: how many subsets of the values seen so far add up to s
ways = [0] * (goal + 1)
ways[0] = 1
for x in nums:
# From the top down, so each value is used at most once
for s in range(goal, x - 1, -1):
ways[s] += ways[s - x]
return ways[goal]
Ловушки и крайние случаи
- Пропуск проверки чётности. Для
[6, 3]и целевого значения 4 число(9 + 4) / 2округляется вниз до 6, а подмножество{6}даёт 1 вместо 0. - Пропуск проверки диапазона. Для
[1, 2, 3]и целевого значения -10 получаем(6 - 10) / 2 = -2— отрицательный размер массива. - Заполнение
waysснизу вверх. Тогда число добавляется в подмножество, в котором оно уже используется: для[1, 3]с целевым значением 2 алгоритм выдаёт 2 вместо 1. - Считать ноль одним вариантом выбора. Для
[0, 0, 0, 1, 0, 0]с целевым значением -1 есть 32 ответа — по одному для каждого сочетания знаков у пяти нулей. - Использование отрицательной текущей суммы в качестве индекса для мемоизации. Сдвиньте каждую сумму на
Sили используйте хеш-таблицу.
Частые вопросы3
Как задача Target Sum связана с задачей о сумме подмножества?
Числа со знаком плюс должны в сумме давать (S + target) / 2, поэтому ответ — это количество подмножеств nums с такой суммой. Эту задачу решит любой алгоритм динамического программирования для подсчёта подмножеств с заданной суммой, если добавить две проверки: значение должно быть целым числом, а |target| не должно превышать S.
Какова временная сложность задачи Target Sum?
Динамическое программирование для подсчёта подмножеств работает за время O(n × S) и использует O(S) памяти, где S — сумма nums. Рекурсия с мемоизацией имеет такую же временную сложность, но использует таблицу размером n × (2S+1). Перебор всех знаков занимает O(2^n).
Можно ли решить задачу Target Sum с помощью хеш-таблицы текущих сумм?
Да. Сопоставьте каждой достижимой текущей сумме количество префиксов знаков, которые к ней приводят, начиная с {0: 1}, и постройте следующую карту из total + x и total - x для каждого числа. Ответ — количество для target. Это мемоизированная рекурсия, выполняемая вперёд, за то же время O(n × S).
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def findTargetSumWays(nums, target):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргументы
nums = [2, 1, 1] target = 2
Ожидаемый вывод
2