Целевая сумма с положительными и отрицательными знаками

Дан целочисленный массив nums и целое число target. Назначьте каждому числу знак + или -, чтобы получившееся выражение имело значение target. Верните количество различных способов это сделать. Например, для nums=[1,1,1,1,1] и target=3 существует 5 способов: выбрать 4 положительных элемента и 1 отрицательный, причём отрицательный элемент может находиться на разных позициях.

Подход с DFS присваивает каждому числу знак + или - и рекурсивно перебирает варианты, возвращая количество конечных вершин, в которых достигнуто значение target. Решение корректно, но имеет временную сложность O(2^n) — она экспоненциальна. При n=20 это более миллиона рекурсивных вызовов. На собеседовании стоит сначала упомянуть подход с DFS, а затем быстро перейти к оптимизации с помощью DP.

Добавим мемоизацию в DFS: состояние задаётся как (index, current_sum). Поскольку текущая сумма может находиться в диапазоне от -total до +total, существует O(n × total) уникальных состояний. С мемоизацией DFS работает за время и с использованием O(n × total) памяти. Этот подход корректен и допустим на собеседовании, но DP на основе преобразования элегантнее и эффективнее по памяти.

Пусть P — множество чисел, которым присвоен знак +, а N — множество чисел со знаком -. Тогда: sum(P) - sum(N) = target и sum(P) + sum(N) = total. Складывая эти равенства, получаем: 2 × sum(P) = target + total, поэтому sum(P) = (target + total) / 2. Задача сводится к следующей: подсчитать подмножества nums с суммой (целевая сумма + общая сумма) / 2. Это ровно вариант задачи о рюкзаке 0/1 с подсчётом подмножеств.

Перед запуском DP проверьте: (1) target + total должно быть чётным, иначе sum(P) не будет целым числом и решение невозможно; (2) если abs(target) > total, целевую сумму нельзя получить даже при одинаковом направлении всех знаков. Если любая проверка не пройдена, немедленно верните 0. Эти проверки аккуратно обрабатывают граничные случаи без специальных условий внутри цикла DP.

Для nums=[1,1,1,1,1] и target=3: общая сумма = 5, новая целевая сумма = (3+5)//2 = 4. Мы подсчитываем подмножества с суммой 4 в массиве [1,1,1,1,1]. Это C(5,4)=5: выбираем 4 единицы со знаком плюс, а пятую — со знаком минус, поэтому 1+1+1+1-1=3. DP правильно возвращает 5. Это преобразование элегантно сводит задачу о присваивании знаков к стандартной задаче подсчёта подмножеств.

Если nums содержит нули, присваивание нулю знака + или - не меняет сумму. Каждый ноль удваивает количество допустимых присваиваний. DP естественным образом это учитывает: при обработке num=0 внутренний цикл range(new_target, -1, -1) идёт от new_target до 0, а выражение dp[c] += dp[c - 0] = dp[c] удваивает все достижимые суммы. Специальная обработка не нужна, если используется range(new_target, num-1, -1), который при num=0 начинается с new_target и идёт до 0.

Полный перебор с DFS имеет сложность O(2^n). DFS с мемоизацией работает за O(n × total) времени и использует O(n × total) памяти. Одномерный DP на основе преобразования работает за O(n × new_target) времени и использует O(new_target) памяти, где new_target ≤ total. Одномерный DP требует значительно меньше памяти, чем мемоизация, поскольку преобразование устраняет измерение индекса.

Задача о целевой сумме объединяет несколько концепций задач о рюкзаке: сначала это задача о присваивании знаков, затем она преобразуется в задачу о сумме подмножеств (как задача о равном разбиении на подмножества) и использует тот же шаблон обратного перебора в задаче о рюкзаке 0/1, но с подсчётом вариантов (как в задаче о размене монет II). Освоив эти связи, вы сможете быстро классифицировать новые задачи на собеседованиях по их структурному сходству с известными шаблонами.

Ключевые случаи: (1) target = total: существует только один способ — все знаки положительные; (2) target = -total: существует только один способ — все знаки отрицательные; (3) target = 0 при состоящем только из нулей массиве: ответ равен 2^n; (4) очень большая общая сумма при небольшом n — размер одномерного массива DP ограничен значением total/2. На собеседовании сначала проговорите этап преобразования, а уже затем пишите код: именно это неочевидное наблюдение отличает сильных кандидатов.

Без преобразования определим dp[i][s] как количество способов назначить знаки первым i числам так, чтобы получить сумму s. Сумма может быть отрицательной, поэтому используйте смещение на общую сумму: dp[i][s + total]. Для этого потребуется двумерная таблица размера (n+1) × (2*total+1). Хотя этот подход корректен, он требует больше памяти и его сложнее быстро реализовать под давлением на собеседовании, чем одномерную задачу о рюкзаке после преобразования.

Проверьте, насколько вы усвоили концепции структур данных и алгоритмов — подготовки к собеседованию по программированию, рассмотренные в этом уроке.

В этом уроке вы узнали: задача о целевой сумме преобразуется в подсчёт подмножеств с суммой (целевая сумма + общая сумма) / 2, обратный перебор в одномерной задаче о рюкзаке 0/1 подсчитывает подмножества за время O(n × размера новой цели) и с использованием O(размера новой цели) памяти, а ранние проверки корректности (нечётная сумма, абсолютное значение целевой суммы больше общей суммы) предотвращают ненужный запуск DP. Далее мы перейдём к поиску кратчайших путей с алгоритмом Дейкстры и очередью с приоритетами.