Сегодня нам предстоит решить задачу 494. Target Sum.
Описание задачи 📜
Нам дана последовательность чисел nums и целевая сумма target.
Необходимо определить количество способов поставить знаки + или - перед числами так, чтобы выражение из всех чисел дало в результате target.
Пример
Для nums = [1, 1, 1, 1, 1] и target = 3, всего 5 правильных комбинаций:
-1+1+1+1+1+1-1+1+1+1+1+1-1+1+1+1+1+1-1+1+1+1+1+1-1
Идея 💡
Эту задачу можно свести к известной задаче о рюкзаке:
-
Разделим числа на две группы:
Sum_Positive — сумма чисел со знаком +,Sum_Negative — сумма чисел со знаком -.
-
Из уравнений:
Sum_Positive − Sum_Negative = Target- и
Sum_Positive + Sum_Negative = Total_Sum
-
Выводим:
2⋅Sum_Negative = Total_Sum − Target
-
Таким образом, задача сводится к подсчету способов выбрать подмножество чисел, сумма которых равна
(Total_Sum−Target)/2.
Детали подхода 🚀
-
Ограничение диапазона:
- После преобразования все возможные суммы ограничиваются диапазоном от 0 до Total_Sum и должны быть чётными. Это сразу ограничевает диапазон корректных таргетов.
-
Динамическое программирование:
- Используем массив
n_sums, где n_sums[x] хранит количество способов получить сумму x.
- Базовый случай:
n_sums[0] = 1 (один способ получить сумму 0 — ничего не выбирать).
- Итеративно обновляем массив, добавляя текущее число из
nums ко всем ранее возможным суммам.
- Для предотвращения использования перезаписанных значений итерация проводится с больших сумм к меньшим.
-
Проверка целевого значения:
- Если
Total_Sum−Target нечетное (согласно замечанию из пункта 1) или выходит за границы, возвращаем 0 — решений нет.
Асимптотика ⏱️
- Время:
O(n⋅MAX_SUM),
- где
n — длина nums, а MAX_SUM — максимальная сумма всех чисел (ограничена по условию 1000).
- Память:
O(MAX_SUM)
- Храним только массив
n_sums для текущих состояний.
Исходный код 🧑💻
impl Solution {
pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
const MAX_SUM: usize = 1000; // Maximum possible sum constraint
// Initialize a dynamic programming array to store the number of ways to achieve each sum
let mut n_sums = vec![0; MAX_SUM + 1];
n_sums[0] = 1; // Base case: one way to achieve sum = 0
let mut total_sum = 0;
for &num in &nums {
if num < 0 || num as usize > MAX_SUM {
panic!("Input number {} is out of range [0, {}]", num, MAX_SUM);
}
total_sum += num;
if total_sum > MAX_SUM as i32 {
panic!("Total sum {} exceeds the maximum allowed value of {}", total_sum, MAX_SUM);
}
// Iterate from total_sum down to 0 to prevent overwriting the current state
for sum in (0..=total_sum - num).rev() {
let new_sum = sum + num;
n_sums[new_sum as usize] += n_sums[sum as usize];
}
}
// Validate the target's feasibility
let adjusted_target = total_sum - target;
if target < -total_sum || target > total_sum || adjusted_target % 2 != 0 {
return 0; // No valid expressions exist
}
// Return the number of ways to achieve the adjusted target
n_sums[(adjusted_target / 2) as usize]
}
}