Liệt kê dãy ngoặc đúng - LCOJ: Luyện Code Online Judge

PTIT015 - Liệt kê dãy ngoặc đúng

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Định nghĩa khái niệm dãy ngoặc đúng dưới dạng đệ quy như sau:

() là dãy ngoặc đúng
C là dãy ngoặc đúng nếu C = (A) hay C = AB với A, B là các dãy ngoặc đúng.

Ví dụ dãy ngoặc đúng: (), (()), ()(), (())()
Ví dụ dãy ngoặc sai: )(, ((((, ()((, )))), )()(

Bạn hãy viết chương trình liệt kê tất cả các dãy ngoặc đúng có chiều dài ~n~ (~n~ chẵn)

Input

Là số nguyên ~n~ (~n~ chẵn, ~2 ≤ n ≤ 20~)

Output

với ~m~ là số lượng các dãy ngoặc đúng có chiều dài ~n~

Trong m dòng đầu tiên, mỗi dòng liệt kê một dãy ngoặc đúng chiều dài ~n~. Các dãy được liệt kê theo thứ tự từ điển: '(' nhỏ hơn ')'.
Dòng cuối cùng là số ~m~

Sample

Input #1

Output #1

(())
()()
2

Problem source: CLB Lập Trình PTIT

Bình luận

Please read the guidelines before commenting.

sinh bằng đệ quy

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
string p = "()";
const int maxn = 20;
int n;
vector<char> s(maxn);
vector<string> ans;
bool check() {
    stack<char> st;
    int counto = 0, countc = 0;
    for(int i = 0; i < n; i++) {
        if(s[i] == '(') {
            counto++;
            st.push(s[i]);
        }
        else {
            if(st.empty()) return false;
            st.pop();
            countc++;
        }
    }
    return counto == countc;
}
void Try(int x) {
    for(int i = 0; i < 2; i++) {
        if(i == 0) s[x] = '(';
        else s[x] = ')';
        if(x == n - 1) {
            if(check()) {
                string se = "";
                for(int j = 0; j < n; j++) {
                    se = se + s[j];
                }
                ans.push_back(se);
            }
        }
        else Try(x+1);
    }
}
void AC() {
    cin >> n;
    Try(0);
    for(int i = 0; i < ans.size(); i++) {
        cout << ans[i] << '\n';
    }
    cout << ans.size();
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    AC();
    return 0;
}

0

MrDat đã bình luận lúc 31, Tháng 5, 2025, 10:39

làm sao để post soủce code vậy mọi người, em có post mà nó không cho