Сложность: medium
Вам дан массив целых чисел 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 {
var count = 0
func findTargetSumWays(_ nums: [Int], _ S: Int) -> Int {
calculate(nums, 0, 0, S)
return count
}
func calculate(_ nums: [Int], _ i: Int, _ sum: Int, _ S: Int) {
if i == nums.count {
if sum == S {
count += 1
}
} else {
calculate(nums, i + 1, sum + nums[i], S)
calculate(nums, i + 1, sum - nums[i], S)
}
}
}Ставь 👍 и забирай 📚 Базу знаний