Задача: 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 {
    private $answer;
    private $digits;
    private $target;

    private function recurse($index, $previousOperand, $currentOperand, $value, &$ops) {
        if ($index == strlen($this->digits)) {
            if ($value == $this->target && $currentOperand == 0) {
                $this->answer[] = implode("", $ops);
            }
            return;
        }

        $currentOperand = $currentOperand * 10 + intval($this->digits[$index]);
        $currentValRep = strval($currentOperand);

        if ($currentOperand > 0) {
            $this->recurse($index + 1, $previousOperand, $currentOperand, $value, $ops);
        }

        $ops[] = "+";
        $ops[] = $currentValRep;
        $this->recurse($index + 1, $currentOperand, 0, $value + $currentOperand, $ops);
        array_pop($ops);
        array_pop($ops);

        if (count($ops) > 0) {
            $ops[] = "-";
            $ops[] = $currentValRep;
            $this->recurse($index + 1, -$currentOperand, 0, $value - $currentOperand, $ops);
            array_pop($ops);
            array_pop($ops);

            $ops[] = "*";
            $ops[] = $currentValRep;
            $this->recurse($index + 1, $currentOperand * $previousOperand, 0, $value - $previousOperand + ($currentOperand * $previousOperand), $ops);
            array_pop($ops);
            array_pop($ops);
        }
    }

    public function addOperators($num, $target) {
        if (strlen($num) == 0) {
            return [];
        }

        $this->target = $target;
        $this->digits = $num;
        $this->answer = [];
        $ops = [];
        $this->recurse(0, 0, 0, 0, $ops);
        return $this->answer;
    }
}

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