Задача: 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⃣Запускаем рекурсивный обход строк с учётом всех возможных разбиений чисел и вставок операторов.

2⃣Внутри рекурсии рассматривают 4 стороны: продолжить текущее число (без учета вставок оператора), вставить +, -, *.

3⃣Если дошли до конца строки и текущее значение выражения соответствует target, записываем выражение в результат.

😎 Решение:

using System;
using System.Collections.Generic;
using System.Text;

public class Solution {
    public List<string> answer;
    public string digits;
    public long target;

    public void Recurse(int index, long previousOperand, long currentOperand, long value, List<string> ops) {
        if (index == digits.Length) {
            if (value == target && currentOperand == 0) {
                StringBuilder sb = new StringBuilder();
                for (int i = 1; i < ops.Count; i++) {
                    sb.Append(ops[i]);
                }
                answer.Add(sb.ToString());
            }
            return;
        }

        currentOperand = currentOperand * 10 + (digits[index] - '0');
        string currentValRep = currentOperand.ToString();

        if (currentOperand > 0) {
            Recurse(index + 1, previousOperand, currentOperand, value, ops);
        }

        ops.Add("+");
        ops.Add(currentValRep);
        Recurse(index + 1, currentOperand, 0, value + currentOperand, ops);
        ops.RemoveAt(ops.Count - 1);
        ops.RemoveAt(ops.Count - 1);

        if (ops.Count > 0) {
            ops.Add("-");
            ops.Add(currentValRep);
            Recurse(index + 1, -currentOperand, 0, value - currentOperand, ops);
            ops.RemoveAt(ops.Count - 1);
            ops.RemoveAt(ops.Count - 1);

            ops.Add("*");
            ops.Add(currentValRep);
            Recurse(index + 1, currentOperand * previousOperand, 0, value - previousOperand + (currentOperand * previousOperand), ops);
            ops.RemoveAt(ops.Count - 1);
            ops.RemoveAt(ops.Count - 1);
        }
    }

    public IList<string> AddOperators(string num, int target) {
        if (num.Length == 0) {
            return new List<string>();
        }

        this.target = target;
        this.digits = num;
        this.answer = new List<string>();
        Recurse(0, 0, 0, 0, new List<string>());
        return answer;
    }
}

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