Задача: 494. Target Sum
Вам дан массив целых чисел nums и целое число target.
Вы хотите создать выражение из nums, добавляя один из символов '+' или '-' перед каждым числом в nums, а затем объединяя все числа.
Например, если nums = [2, 1], вы можете добавить '+' перед 2 и '-' перед 1, а затем объединить их, чтобы получить выражение "+2-1".
Верните количество различных выражений, которые можно построить и которые оцениваются в target.
Пример:
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
👨💻 Алгоритм:
1⃣Инициализация и вызов рекурсивной функции
Создайте переменную для хранения количества решений (count). Вызовите рекурсивную функцию calculate с начальными параметрами (nums, начальный индекс 0, начальная сумма 0, и target).
2⃣Рекурсивная функция calculate
Если текущий индекс равен длине массива, проверьте, равна ли текущая сумма значению target. Если да, увеличьте счетчик решений. В противном случае, вызовите функцию рекурсивно дважды: добавляя и вычитая текущее значение из суммы.
3⃣Возврат результата
После завершения всех рекурсивных вызовов верните значение счетчика решений.
😎 Решение:
class Solution {
private $count = 0;
function findTargetSumWays($nums, $S) {
$this->calculate($nums, 0, 0, $S);
return $this->count;
}
private function calculate($nums, $i, $sum, $S) {
if ($i == count($nums)) {
if ($sum == $S) {
$this->count++;
}
} else {
$this->calculate($nums, $i + 1, $sum + $nums[$i], $S);
$this->calculate($nums, $i + 1, $sum - $nums[$i], $S);
}
}
}👉Новости 👉База вопросов
