Xóa ngoặc không hợp lệ để tạo biểu thức hợp lệ bằng C++

Cho chuỗi ngoặc, xóa tối thiểu số ngoặc để được tất cả biểu thức hợp lệ có thể. In tất cả kết quả khác nhau. Ví dụ:

Input: "()())()" → Output: ()()()  (())() Input: "(v)())()" → Output: (v)()()  (v())()

Cách tiếp cận: BFS + Backtracking
Dùng BFS trên không gian trạng thái (mỗi trạng thái = chuỗi sau khi xóa 1 ngoặc). Dùng set tránh lặp. Khi tìm thấy chuỗi hợp lệ ở mức nào đó, in tất cả chuỗi hợp lệ ở mức đó và dừng (đảm bảo xóa ít nhất).
Ví dụ
#include <bits/stdc++.h>
using namespace std;

bool isParenthesis(char c) { return c == '(' || c == ')'; }

bool validString(string str) {
    int cnt = 0;
    for (char c : str) {
        if (c == '(') cnt++;
        else if (c == ')') cnt--;
        if (cnt < 0) return false;
    }
    return cnt == 0;
}

void validParenthesesSequences(string str) {
    if (str.empty()) return;
    set visit;
    queue q;
    q.push(str); visit.insert(str);
    bool level = false;
    while (!q.empty()) {
        str = q.front(); q.pop();
        if (validString(str)) {
            cout << str << "\n";
            level = true;
        }
        if (level) continue;
        for (int i = 0; i < str.length(); i++) {
            if (!isParenthesis(str[i])) continue;
            string temp = str.substr(0, i) + str.substr(i + 1);
            if (visit.find(temp) == visit.end()) {
                q.push(temp); visit.insert(temp);
            }
        }
    }
}

int main() {
    string s1 = "(v)())()";
    cout << "Input : " << s1 << "\nOutput : ";
    validParenthesesSequences(s1);
    return 0;
}
Kết quả
Input : (v)())() Output : (v())()
Kết luận
Tìm tất cả biểu thức ngoặc hợp lệ bằng cách xóa ít nhất ngoặc: BFS trên không gian trạng thái + kiểm tra hợp lệ. Code C++.