เพิ่มตัวดำเนินการในสตริงเพื่อให้ได้ค่าเป้าหมายใน C++ (Expression Add Operators)

ภาพรวมปัญหา

ให้สตริงตัวเลข และค่าเป้าหมาย target ใส่ +, -, * ระหว่างตัวเลข เพื่อให้สมการได้ค่า target คืนคำตอบทั้งหมด

ตัวอย่าง

num = "232", target = 8 → ["2*3+2", "2+3*2"]

วิธีแก้ปัญหา: Backtracking (DFS)

ลองตัดสตริงเป็น operand ตัวต่างๆ แล้วลองวาง operator 3 แบบ
ใช้ curr = ค่าปัจจุบัน, mult = ตัวคูณล่าสุด (เพื่อจัดการ precedence ของ *)

การจัดการ precedence

• +: curr + val, mult = val
• -: curr - val, mult = -val
• *: curr - mult + mult × val, mult = mult × val

โค้ด C++

#include <bits/stdc++.h>
using namespace std;
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; // no leading zeros
            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));
}

การวิเคราะห์ความซับซ้อน

• เวลา: O(4ⁿ) — แต่ละตำแหน่งมี 4 ทางเลือก (concat, +, -, *)
• พื้นที่: O(n) — recursion depth