Задача: 282. Expression Add Operators
Сложность: hard

Дана строка num, содержащая только цифры, и целое число target. Верните все возможные варианты вставки бинарных операторов '+', '-', и/или '*' между цифрами строки num так, чтобы результирующее выражение вычислялось в значение target.

Учтите, что операнды в возвращаемых выражениях не должны содержать ведущих нулей.

Пример:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

👨‍💻 Алгоритм:

1⃣Инициализация и рекурсивный вызов:
Создайте класс Solution с полями для хранения результирующих выражений, строки цифр и целевого значения.
Инициализируйте эти поля в методе addOperators и запустите рекурсивный метод для генерации всех возможных выражений.

2⃣Рекурсивная генерация выражений:
В методе recurse на каждом шаге рассматривайте текущий индекс, предыдущий операнд, текущий операнд и текущее значение выражения.
Обрабатывайте все возможные операторы: без оператора (расширение текущего операнда), сложение, вычитание и умножение. На каждом шаге обновляйте текущее значение и выражение.

3⃣Проверка и запись валидных выражений:
Когда вся строка цифр обработана, проверяйте, соответствует ли итоговое значение целевому значению и нет ли остатков операндов.
Если выражение валидное, записывайте его в список результатов.

😎 Решение:

class Solution {
    var answer = [String]()
    var digits = ""
    var target: Int64 = 0

    func recurse(_ index: Int, _ previousOperand: Int64, _ currentOperand: Int64, _ value: Int64, _ ops: inout [String]) {
        if index == digits.count {
            if value == target && currentOperand == 0 {
                answer.append(ops.joined())
            }
            return
        }

        let nums = Array(digits)
        let currentDigit = Int64(String(nums[index]))!
        let currentOperand = currentOperand * 10 + currentDigit
        let currentValRep = String(currentOperand)

        if currentOperand > 0 {
            recurse(index + 1, previousOperand, currentOperand, value, &ops)
        }

        ops.append("+")
        ops.append(currentValRep)
        recurse(index + 1, currentOperand, 0, value + currentOperand, &ops)
        ops.removeLast(2)

        if !ops.isEmpty {
            ops.append("-")
            ops.append(currentValRep)
            recurse(index + 1, -currentOperand, 0, value - currentOperand, &ops)
            ops.removeLast(2)

            ops.append("*")
            ops.append(currentValRep)
            recurse(index + 1, currentOperand * previousOperand, 0, value - previousOperand + (currentOperand * previousOperand), &ops)
            ops.removeLast(2)
        }
    }

    func addOperators(_ num: String, _ target: Int) -> [String] {
        if num.isEmpty {
            return []
        }

        self.target = Int64(target)
        self.digits = num
        self.answer = []
        var ops = [String]()
        recurse(0, 0, 0, 0, &ops)
        return answer
    }
}

Ставь 👍 и забирай 📚 Базу знаний