Thêm toán tử biểu thức (Expression Add Operators) trong C++

Cho chuỗi chỉ chứa chữ số 0-9 và giá trị target. Chèn +, -, * giữa các chữ số để tạo biểu thức bằng target. Trả về tất cả biểu thức hợp lệ.

Ví dụ

num = "232", target = 8

Kết quả: ["2*3+2", "2+3*2"]

Thuật toán: Backtracking (DFS)

Duyệt từng vị trí cắt chuỗi con, thử 3 toán tử. Cần xử lý độ ưu tiên của * (nhân trước cộng/trừ).

Trạng thái DFS

• idx: vị trí hiện tại trong chuỗi.
• curr: giá trị biểu thức tính đến hiện tại.
• mult: giá trị của operand cuối cùng (dùng để xử lý * — hoàn tác phép cộng/trừ trước đó).
• temp: chuỗi biểu thức đang xây dựng.

Xử lý phép nhân

Khi thêm * val:

new_curr = curr - mult + mult * val
new_mult = mult * val

Ví dụ: 2+3*2: khi ở 2+3 (curr=5, mult=3), thêm *2 → 5 - 3 + 3*2 = 8.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<string> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

typedef long long int lli;

class Solution {
public:
    vector<string> ret;

    void solve(int idx, string s, lli curr, lli target, string temp, lli mult) {
        if (idx >= s.size()) {
            if (target == curr) ret.push_back(temp);
            return;
        }
        string aux = "";
        for (int i = idx; i < s.size(); i++) {
            aux += s[i];
            if (aux[0] == '0' && aux.size() > 1) continue; // bỏ qua số dẫn 0
            if (idx == 0) {
                solve(i + 1, s, stoll(aux), target, aux, stoll(aux));
            } else {
                solve(i + 1, s, curr + stoll(aux), target, temp + "+" + aux, stoll(aux));
                solve(i + 1, s, curr - stoll(aux), target, temp + "-" + aux, -stoll(aux));
                solve(i + 1, s, curr - mult + mult * stoll(aux), target, temp + "*" + aux, mult * stoll(aux));
            }
        }
    }

    vector<string> addOperators(string num, int target) {
        solve(0, num, 0, target, "", 0);
        return ret;
    }
};

int main() {
    Solution ob;
    print_vector(ob.addOperators("232", 8));
    return 0;
}

Độ phức tạp

• Thời gian: O(4^n) worst-case (mỗi vị trí có 4 lựa chọn: không cắt, +, -, *). Thực tế nhanh nhờ cắt tỉa.
• Không gian: O(n) đệ quy + O(k) kết quả.

Input / Output

Input:  "232", 8
Output: [2+3*2, 2*3+2]