พิมพ์นิพจน์ทั้งหมดที่ให้ค่าเป้าหมายใน C++

ปัญหา

ได้รับสตริงตัวเลข 0-9 และค่าเป้าหมาย (Target) พิมพ์นิพจน์ที่ใส่ +, -, * ระหว่างหลักเลข ให้ค่าเท่ากับ Target เช่น "123", target=6 → "1+2+3", "1*2*3"

วิธีแก้

สร้างนิพจน์โดยวาง Operator ทุกความเป็นไปได้ระหว่างหลักเลข ตรวจสอบผลลัพธ์กับ Target ใช้ Recursive Evaluate ถ้าหลักนำเป็น 0 ข้าม

ตัวอย่างโค้ด

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

void generateExpressionForTarget(vector<string>& res, string curExp, string input, int target, int pos, int curVal, int 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;
        string part = input.substr(pos, i + 1 - pos);
        int cur = atoi(part.c_str());
        if (pos == 0)
            generateExpressionForTarget(res, curExp + 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;
    cout << "The expressions are: \n";
    vector<string> res = generateExpression(input, target);
    for (int i = 0; i < res.size(); i++) cout << res[i] << " ";
    cout << endl;
    return 0;
}

ผลลัพธ์

3+4+5

คำอธิบาย

Recursive Function พารามิเตอร์:

• curExp: นิพจน์ที่สร้างอยู่
• pos: ตำแหน่งปัจจุบันในสตริง
• curVal: ค่าปัจจุบันของนิพจน์
• last: ตัวถูกคูณล่าสุด (สำหรับ Handle Operator Precedence ของ *)

การคูณ: curVal - last + last * cur (ยกเลิก last เดิม แล้วคูณ last*cur)

ตัวอย่าง "345" target=12 → "3+4+5" = 12