In tất cả biểu thức đánh giá bằng target từ chuỗi số C++

Cho chuỗi số (0-9) và target. Chèn toán tử +, -, * giữa các chữ số để tạo biểu thức giá trị = target.

Ví dụ

Input: "123", target = 6 → Output: "1+2+3", "1*2*3"

Thuật toán Backtracking

Duyệt mọi cách chèn toán tử giữa các chữ số. Đệ quy với tham số: vị trí hiện tại, giá trị hiện tại, giá trị operand cuối (cho phép nhân ưu tiên).

Xử lý độ ưu tiên nhân (*)

Khi gặp '*': undo phép cộng/trừ cuối, nhân với operand mới.

new_val = curVal - last + last * cur

Chương trình mẫu

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

void generateExpressionForTarget(vector<string>& res, string curExp, string input, 
                                 int target, int pos, long curVal, long last) {
    if (pos == input.length()) {
        if (curVal == target) res.push_back(curExp);
        return;
    }
    for (int i = pos; i < input.length(); i++) {
        if (i != pos && input[pos] == '0') break; // Bỏ qua số dẫn đầu 0
        string part = input.substr(pos, i - pos + 1);
        long cur = stol(part);
        if (pos == 0) {
            generateExpressionForTarget(res, part, input, target, i + 1, cur, cur);
        } else {
            generateExpressionForTarget(res, curExp + "+" + part, input, target, i + 1, curVal + cur, cur);
            generateExpressionForTarget(res, curExp + "-" + part, input, target, i + 1, curVal - cur, -cur);
            generateExpressionForTarget(res, curExp + "*" + part, input, target, i + 1, curVal - last + last * cur, last * cur);
        }
    }
}

vector<string> generateExpression(string input, int target) {
    vector<string> res;
    generateExpressionForTarget(res, "", input, target, 0, 0, 0);
    return res;
}

int main() {
    string input = "345";
    int target = 12;
    vector<string> res = generateExpression(input, target);
    cout << "Expressions: ";
    for (string& s : res) cout << s << " ";
    return 0;
}

Kết quả

Expressions: 3+4+5

Giải thích: 3+4+5 = 12. Các biểu thức khác như 3*4+5=17, 34+5=39... không bằng 12.

Độ phức tạp: O(4^n) worst case (4 lựa chọn: nối chữ số, +, -, * tại mỗi vị trí). Dùng long tránh tràn số.